# Big Omega(Ω) Notation

Ω Notation provides the asymptotic lower bound on the function. A function needs to satisfy some conditions in order to be in Ω notation.Ω(g(n)) is the best case running time of function g(n) within a constant factor.

Ω(g(n)) = {f(n): there exist positive constants c and n_{0} such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n_{0}}.It is used to bound the best case running time of an algorithm.g(n) is an asymptotic lower bound for f(n).

Example 1

- Prove that if f(n) = 15n
^{3}+ n^{2}+ 4, then f(n) belongs to Ω(n^{3 }) for all n. - For omega notation,c*g(n) should be less than f(n).
- Here f(n) = 15n
^{3}+ n^{2}+ 1 - g(n) = n
^{3} - Let c=15
- 15 n
^{3}<= 15n^{3}+ n^{2}+ 1 _{n0 =1 }

- 15 n
- f(n) belongs to Ω class.
- Ω is the lower bound.

Example 2

- Show that 2n +7 is Ω(n) .
- f(n) = 2n + 7
- g(n) = 2n
- c * g(n) <= f(n)
- c*2n <=2n+7
- Let c=2
- 4n<=2n+7
- 2n<=7
- n<=7/2

- Thus for c=2 and n
_{0}= 7/2 f(n) belongs to Ω(n).

## Comments

So empty here ... leave a comment!