• Create Account

## Confused on Little Oh

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

3 replies to this topic

### #1warnexus  Prime Members

1535
Like
0Likes
Like

Posted 16 March 2013 - 09:25 AM

I was reading the Little Oh notation in a textbook. Apparently it has two meanings:

1) f(x) is Big-Oh (gx)  which means f(x) <= g(x)

2) f(x) is NOT Big-Theta g(x)^4. (This definition confused me a lot.)

In my own words this would mean: f(x) <= g(x). Since Big Theta is Big Oh and Big Omega combined. f(x) is NOT <= g(x)^4 would mean f(x) is > g(x)^4 and f(x) is NOT >= g(x)^4 which mean f(x) is < g(x) ^ 4. Based on what I said, wouldn't the second definition actually mean f(x) is Big Theta g(x)^4?

Please correct me if I'm wrong.

Edited by warnexus, 16 March 2013 - 09:30 AM.

### #2Steve_Segreto  Members

2008
Like
0Likes
Like

Posted 17 March 2013 - 11:57 AM

I don't know about your second question, but the first statement where you rephrased f(x) = o(g(x)) into your own words is a bit off. f(x) < g(x) for all x. Not <=. f(x) is inferiorly less than g(x) for all x. That's the definition of little-oh.

### #3warnexus  Prime Members

1535
Like
0Likes
Like

Posted 17 March 2013 - 06:56 PM

Thanks Steve for the correct definition. It is much easier to remember.

### #4snowmanZOMG  Members

1205
Like
0Likes
Like

Posted 17 March 2013 - 07:23 PM

Your question is impossible for me to comprehend.  Little O has a very precise meaning.

http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations

The key difference between Big O and Little O is that there's some notion of bounds tightness in Big O that is not necessary for Little O.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.