Big O is giving only upper asymptotic bound, while big Theta is also giving a lower bound.
Everything that is Theta(f(n))
is also O(f(n))
, but not the other way around.
T(n)
is said to be Theta(f(n))
, if it is both O(f(n))
and Omega(f(n))
For this reason big-Theta is more informative than big-O notation, so if we can say something is big-Theta, it's usually preferred. However, it is harder to prove something is big Theta, than to prove it is big-O.
For example, merge sort is both O(n*log(n))
and Theta(n*log(n))
, but it is also O(n2), since n2 is asymptotically "bigger" than it. However, it is NOT Theta(n2), Since the algorithm is NOT Omega(n2).
Omega(n)
is asymptotic lower bound. If T(n)
is Omega(f(n))
, it means that from a certain n0
, there is a constant C1
such that T(n) >= C1 * f(n)
. Whereas big-O says there is a constant C2
such that T(n) <= C2 * f(n))
.
All three (Omega, O, Theta) give only asymptotic information ("for large input"):
- Big O gives upper bound
- Big Omega gives lower bound and
- Big Theta gives both lower and upper bounds
Note that this notation is not related to the best, worst and average cases analysis of algorithms. Each one of these can be applied to each analysis.
Theta(f(n))
if the worst case and best case are identical, we say it isTheta(f(n))
worst case (for example), if the worst case is bothO(f(n))
andOmega(f(n))
, regardless of the behavior of the best case.Theta(n^2)
, since you can give a lower bound on how many ops will be needed on a worst case input (reversed order array), and it will be quadric in the number of elements. There is no sense talking about complexity of an algorithm without indicating under what analyzis it is calculated. Usually when the analyzis is omitted - it implicitly means that the complexity is calculated under the worst case analyzis. If we use this convention, insertion sort isTheta(n^2)
[worst case analyzis is implicit in this claim].