Jump to content

  • Log In with Google      Sign In   
  • 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.

  • You cannot reply to this topic
3 replies to this topic

#1 warnexus   Prime Members   -  Reputation: 1384

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. sleep.png 


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


Sponsor:

#2 Steve_Segreto   Crossbones+   -  Reputation: 1475

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.



#3 warnexus   Prime Members   -  Reputation: 1384

Like
0Likes
Like

Posted 17 March 2013 - 06:56 PM

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



#4 snowmanZOMG   Members   -  Reputation: 813

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.



PARTNERS