Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!

# combining big Oh with bit Theta

jay vas
Ranch Hand
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
Posts: 5432
52
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).

jay vas
Ranch Hand
Posts: 407
Hmmm okay... So I guess a "tight" bound is when omega=theta ?

Stephan van Hulst
Bartender
Posts: 5432
52
A bound g(n) is tight if it's in O(f(n)) and Omega(f(n)) and thus in Theta(f(n)).