Asymptotic Notations- Big Omega Notation [Ω] & Big Theta Notation [Ѳ]

In the previous post we have seen the 1. Big O Notation [O]. Next is-

2. Big Omega Notation [Ω]

In opposite to the big O notation this notation represents tightest lower bound of the given function.

Analytically we say as: f(n) belongs to Ω(g(n)) as there exists c > 0 (e.g., c = 1) and n0 (e.g. n0 = 5) such that f(n) ≥ c.g(n) whenever n ≥ n0.

Example- lets find tightest lower bound of f(n) = 5n²+2n+1.

By looking to f(n) we can say that if we have a function g(n) = n²  (As, n²  is always less than 5n²) then it will be the tightest lower bound of f(n). In other words: f(n) ≥ c.g(n) for c=1 & n0=1. In Big Omega, we say f(n) = Ω(n²) & it is read as "f of n is big omega of n²".

Another thing to note is if f(n) = Ω(n²) then f(n) = Ω(n) or f(n) = Ω(logn) because n & logn are lesser than n²

But since we use Big Omega notation to represent tightest lower bound of the function, we will say f(n) = Ω(n²) instead of Ω(n) or Ω(logn).

Big Omega notation is usually used to specify time/space complexity of the given algorithm in best case scenario. Best case scenario is the situation when algorithm takes the least time to run or the least memory during it's execution.

3. Big Theta Notation [Ѳ]

This notation is used to find average time/space complexity of an algorithm.

Average complexity will always be between tightest upper bound and tightest lower bound.

Analytically we say as: f(n) belongs to Ѳ(g(n)) as there exists c > 0, d > 0 (e.g., c = 1, d=3) and n0 (e.g. n0 = 5) such that c.g(n) ≥ f(n) ≥ d.g(n) whenever n ≥ n0.

Example- suppose, we have a function f(n) = 7n³+2.
Then f(n) = O(n³) for c = 8, n0=2. Also, f(n) = Ω(n³) for c = 6, n0=2. Now as lower & upper bound of f(n) is n³ then we can say average of time complexity for f(n) is n³. Hence, f(n) = Ѳ(n³) & it is read as "f of n is big theta of n³".

General rules while analyzing time complexity:
1. We analyze the time complexity for very large input size.
2. We consider worst case scenario i.e. Big O notation.
3. For any function, f(n) then we drop lower order terms & constant multipliers.
e.g. f(n) = 10n⁴+4n³+n²+2n+5 then f(n) = O(n⁴)
Here, we have dropped lower order terms which are 4n³,n²,2n & 5. We have considered 10n⁴ and finally we omitted 10, which is a constant multiplier & we are left with n^4.