Wednesday, 1 June 2016

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

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

In opposite to the big O notation this notation represents tightest lower bound of the given function.
Big Omega
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) = 5n2+2n+1.

By looking to f(n) we can say that if we have a function g(n) = n2  (As, n2  is always less than 5n2) 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) = Ω(n2) & it is read as "f of n is big omega of n2".

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

But since we use Big Omega notation to represent tightest lower bound of the function, we will say f(n) = Ω(n2) 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.
Big Theta
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) = 7n3+2.
Then f(n) = O(n3) for c = 8, n0=2. Also, f(n) = Ω(n3) for c = 6, n0=2. Now as lower & upper bound of f(n) is n3 then we can say average of time complexity for f(n) is n3. Hence, f(n) = Ѳ(n3& it is read as "f of n is big theta of n3".

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) = 10n4+4n3+n2+2n+5 then f(n) = O(n4)
Here, we have dropped lower order terms which are 4n3,n2,2n & 5. We have considered 10nand finally we omitted 10, which is a constant multiplier & we are left with n4.

No comments:

Post a Comment