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*n*0 (e.g.*n*0 = 5) such that*f*(*n*) ≥*c.**g*(*n*) whenever*n*≥*n*0.
Example- lets find tightest lower bound of f(n) = 5n

^{2}+2n+1.
By looking to f(n) we can say that if we have a function g(n) = n

^{2 }(As, n^{2 }is always less than 5n^{2}) 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^{2}) & it is read as*.***"f of n is big omega of n**^{2}"
Another thing to note is if f(n) = Ω(n

^{2}) then f(n) = Ω(n) or f(n) = Ω(logn) because n & logn are lesser than n^{2}
But since we use Big Omega notation to represent

Big Omega notation is usually used to specify time/space complexity of the given algorithm in

__tightest lower bound__of the function, we will say f(n) = Ω(n^{2}) 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.

Analytically we say as: f(n) belongs to Ѳ(g(n)) as there exists

*c*> 0,*d*> 0 (e.g.,*c*= 1, d=3) and*n*0 (e.g.*n*0 = 5) such that c.*g*(*n*) ≥*f*(*n*) ≥*d.*g(*n*) whenever*n*≥*n*0.^{3}+2.

Then f(n) = O(n

^{3}) for c = 8, n0=2. Also, f(n) = Ω(n

^{3}) for c = 6, n0=2. Now as lower & upper bound of f(n) is n

^{3}then we can say average of time complexity for f(n) is n

^{3}. Hence, f(n) = Ѳ(n

^{3}) & it is read as

*.*

**"f of n is big theta of n**^{3}"**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

^{4}+4n

^{3}+n

^{2}+2n+5 then f(n) = O(n

^{4})

Here, we have dropped lower order terms which are 4n

^{3},n

^{2},2n & 5. We have considered 10n

^{4 }and finally we omitted 10, which is a constant multiplier & we are left with n

^{4.}

^{}

## No comments:

## Post a Comment