I'm really confused about the differences between big O, big Omega, and big Theta notation.
I understand that big O is the upper bound and big Omega is the lower bound, but what exactly does big Ө (theta) represent?
I have read that it means tight bound, but what does that mean?
First let's understand what big O, big Theta and big Omega are. They are all sets of functions.
Big O is giving upper asymptotic bound, while big Omega is giving a lower bound. Big Theta gives both.
Everything that is Ө(f(n)) is also O(f(n)), but not the other way around.
T(n) is said to be in Ө(f(n)) if it is both in O(f(n)) and in Omega(f(n)).
In sets terminology, Ө(f(n)) is the intersection of O(f(n)) and Omega(f(n))
For example, merge sort worst case is both O(n*log(n)) and Omega(n*log(n)) - and thus is also Ө(n*log(n)), but it is also O(n^2), since n^2 is asymptotically "bigger" than it. However, it is not Ө(n^2), Since the algorithm is not Omega(n^2).
O(n) is asymptotic upper bound. If T(n) is O(f(n)), it means that from a certain n0, there is a constant C such that T(n) <= C * f(n). On the other hand, big-Omega says there is a constant C2 such that T(n) >= C2 * f(n))).
Not to be confused with worst, best and average cases analysis: all three (Omega, O, Theta) notation are not related to the best, worst and average cases analysis of algorithms. Each one of these can be applied to each analysis.
We usually use it to analyze complexity of algorithms (like the merge sort example above). When we say "Algorithm A is O(f(n))", what we really mean is "The algorithms complexity under the worst1 case analysis is O(f(n))" - meaning - it scales "similar" (or formally, not worse than) the function f(n).
Well, there are many reasons for it, but I believe the most important of them are:
To demonstrate this issue, have a look at the following graphs:
It is clear that f(n) = 2*n is "worse" than f(n) = n. But the difference is not quite as drastic as it is from the other function. We can see that f(n)=logn quickly getting much lower than the other functions, and f(n) = n^2 is quickly getting much higher than the others.
So - because of the reasons above, we "ignore" the constant factors (2* in the graphs example), and take only the big-O notation.
In the above example, f(n)=n, f(n)=2*n will both be in O(n) and in Omega(n) - and thus will also be in Theta(n).
On the other hand - f(n)=logn will be in O(n) (it is "better" than f(n)=n), but will NOT be in Omega(n) - and thus will also NOT be in Theta(n).
Symmetrically, f(n)=n^2 will be in Omega(n), but NOT in O(n), and thus - is also NOT Theta(n).
1Usually, though not always. when the analysis class (worst, average and best) is missing, we really mean the worst case.
It means that the algorithm is both big-O and big-Omega in the given function.
For example, if it is Ө(n), then there is some constant k, such that your function (run-time, whatever), is larger than n*k for sufficiently large n, and some other constant K such that your function is smaller than n*K for sufficiently large n.
In other words, for sufficiently large n, it is sandwiched between two linear functions :
For k < K and n sufficiently large, n*k < f(n) < n*K
Theta(n): A function f(n) belongs to Theta(g(n)), if there exists positive constants c1 and c2 such that f(n) can be sandwiched between c1(g(n)) and c2(g(n)). i.e it gives both upper and as well as lower bound.
Theta(g(n)) = { f(n) : there exists positive constants c1,c2 and n1 such that 0<=c1(g(n))<=f(n)<=c2(g(n)) for all n>=n1 }
when we say f(n)=c2(g(n)) or f(n)=c1(g(n)) it represents asymptotically tight bound.
O(n): It gives only upper bound (may or may not be tight)
O(g(n)) = { f(n) : there exists positive constants c and n1 such that 0<=f(n)<=cg(n) for all n>=n1}
ex: The bound 2*(n^2) = O(n^2) is asymptotically tight, whereas the bound 2*n = O(n^2) is not asymptotically tight.
o(n): It gives only upper bound (never a tight bound)
the notable difference between O(n) & o(n) is f(n) is less than cg(n) for all n>=n1 but not equal as in O(n).
ex: 2*n = o(n^2), but 2*(n^2) != o(n^2)
I hope this is what you may want to find in the classical CLRS(page 66):
Nothing to mess up buddy!!
If we have a positive valued functions f(n) and g(n) takes a positive valued argument n then ϴ(g(n)) defined as {f(n):there exist constants c1,c2 and n1 for all n>=n1}
where c1 g(n)<=f(n)<=c2 g(n)
let f(n)=5n^2+2n+1
g(n)=n^2
c1=5 and c2=8 and n1=1
Among all the notations ,ϴ notation gives the best intuition about the rate of growth of function because it gives us a tight bound unlike big-oh and big -omega which gives the upper and lower bounds respectively.
ϴ tells us that g(n) is as close as f(n),rate of growth of g(n) is as close to the rate of growth of f(n) as possible.
First of All Theory
Big O = Upper Limit O(n)
Theta = Order Function - theta(n)
Omega = Q-Notation(Lower Limit) Q(n)
In many Blogs & Books How this Statement is emphasised is Like
"This is Big O(n^3)" etc.
and people often Confuse like weather
O(n) == theta(n) == Q(n)
But What Worth keeping in mind is They Are Just Mathematical Function With Names O, Theta & Omega
so they have same General Formula of Polynomial,
Let,
f(n) = 2n4 + 100n2 + 10n + 50 then,
g(n) = n4, So g(n) is Function which Take function as Input and returns Variable with Biggerst Power,
Same f(n) & g(n) for Below all explainations
Big O(n4) = 3n4, Because 3n4 > 2n4
3n4 is value of Big O(n4) Just like f(x) = 3x
n4 is playing a role of x here so,
Replacing n4 with x'so, Big O(x') = 2x', Now we both are happy General Concept is
So 0 ≤ f(n) ≤ O(x')
O(x') = cg(n) = 3n4
Putting Value,
0 ≤ 2n4 + 100n2 + 10n + 50 ≤ 3n4
3n4 is our Upper Bound
Theta(n4) = cg(n) = 2n4 Because 2n4 ≤ Our Example f(n)
2n4 is Value of Theta(n4)
so, 0 ≤ cg(n) ≤ f(n)
0 ≤ 2n4 ≤ 2n4 + 100n2 + 10n + 50
2n4 is our Lower Bound
This is Calculated to find out that weather lower Bound is similar to Upper bound,
Case 1). Upper Bound is Similar to Lower Bound
if Upper Bound is Similar to Lower Bound, The Average Case is Similar
Example, 2n4 ≤ f(x) ≤ 2n4,
Then Theta(n) = 2n4
Case 2). if Upper Bound is not Similar to Lower Bound
In this case, Theta(n) is not fixed but Theta(n) is the set of functions with the same order of growth as g(n).
Example 2n4 ≤ f(x) ≤ 3n4, This is Our Default Case,
Then, Theta(n) = c'n4, is a set of functions with 2 ≤ c' ≤ 3
Hope This Explained!!
I am not sure why there is no short simple answer explaining big theta in plain english (seems like that was the question) so here it is
Big Theta is the range of values or the exact value (if big O and big Omega are equal) within which the operations needed for a function will grow
