The moose likes Programming Diversions and the fly likes combining big Oh with bit Theta Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Introducing JavaFX 8 Programming this week in the JavaFX forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "combining big Oh with bit Theta" Watch "combining big Oh with bit Theta" New topic
Author

combining big Oh with bit Theta

jay vas
Ranch Hand

Joined: Aug 30, 2005
Posts: 407
Hi guys : I've noticed that in some proofs, they combine big Oh notation with big Theta.... I'm not sure, in general, why you would want to express the Upper bound (big Oh) of an algorithm in terms of the lower bound (big theta).....

Any thoughts on the combination of big Oh, horseshoe Oh, and Theta Oh in algorithm analysis ?
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 4086
    
  18

Theta is not lower bound. Omega (or horseshoe, as you call it) is the lower bound. If an algorithm is in Theta for some function, it means that the lower bounds and the upper bound are both described by that function as well.

For instance, if an algorithm is in O(n log n), and it is in Omega(n log n) as well, we say the algorithm is in Theta(n log n).


The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.
jay vas
Ranch Hand

Joined: Aug 30, 2005
Posts: 407
Hmmm okay... So I guess a "tight" bound is when omega=theta ?
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 4086
    
  18

A bound g(n) is tight if it's in O(f(n)) and Omega(f(n)) and thus in Theta(f(n)).
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: combining big Oh with bit Theta
 
It's not a secret anymore!