Asymptotic Notations - Big Omega

Big-Omega is the lower bound of a function is denoted as notation (Ω).

Definition: Suppose we have two functions f(n) and g(n), then the function f(n) = Ω(g(n) if and only if there exists two positive constants c and k, such that f(n) >= c * g(n) for all n >= k

For example:

Suppose, if f(n) = 2 * n + 3, then

2 * n + 3 >= 1 * n for all n >= 0.

In the above equation,
c = 1, k = 0, and g(n) = n

Now we know that, 1< log(n) < n^(1/2) < n < n log(n) < n^2 < n^3 < — < 2^n < 3^n <---- n^n.
In the above comparison, 1< log(n) < n^(1/2) are lower bound.

This symbolizes,

  1. f(n) = Ω(n) — True
  2. f(n) = Ω(n^2) — False
  3. f(n) = Ω(1) — True, and so on…

**Finally, in Big-Omega, we take the nearest g(n), which in this case is Ω(n).