The Omega notation provides a tight lower bound for f(n). This means that the function can never do better than the specified value but it may do worse
Ω notation is simply written as, f(n) ∈ Ω(g(n)), where n is the problem size and
Ω(g(n)) = {h(n): ∃ positive constants c > 0, n0 such that 0 ≤ cg(n) ≤ h(n), ∀ n ≥ n0 }.
Hence, we can say that Ω(g(n)) comprises a set of all the functions h(n) that are greater than or equal to cg(n) for all values of n ≥ n0 .
If cg(n) ≤ f(n), c > O, ∀ n ≥ nO , then f(n) ∈ Ω(g(n)) and g(n) is an asymptotically tight lower bound for f(n)
Examples of functions in Ω(n2 ) include: n2 , n2.9, n3 + n2 , n3