Big Omega

  • Express the mathematical definition of Big Omega.

Big Omega is used to describe asymptotic lower bounds!

$$ T(n) \in \Omega(f(n))\Leftrightarrow \exists \; c > 0, n_0 > 0 \; \; s.t. \; \; T(n) \ge c\cdot f(n) \; \; \forall \; n \ge n_0. $$

Read it as

$T(n)$ is a member of $\Omega(f(n))$ if and only if there exist positive constants $c$ and $n_0$ such that $T(n)\ge c\cdot f(n)$ for all $n\ge n_0$.

$\Omega(f(n))$ is set of functions that grow no slower than $f(n)$.

Here is a pictorial illustration of the above definition:

If you want to prove that $T(n) \in \Omega(f(n))$, you need to choose the constants $c$ and $n_0$ so that above definition holds whenever $n \ge n_0$.

Exercise The running time of an algorithm is $T(n)=7n^2+5$. Show that $T(n) \in \Omega(n^2)$.

Solution

We can choose $c=7$ and $n_0=1$ for the definition of Big Omega to hold.

$$ T(n) = 7n^2 + 5 \ge 7n^2 $$

Resources