Other Common Asymptotic Notations and Why Big O Trumps Them

Big ‘Omega’ - $\Omega(.)$

Mathematically, a function $f(n)$ is in $\Omega(g(n))$ if there exists a real constant $c > 0$ and if there exists $n_o > 0$ such that $f(n) \geq cg(n)$ for $n \geq n_o$. In other words, for sufficiently large values of $n$, $f(n)$ will grow at least as fast as $g(n)$.

It is a common misconception that Big O characterizes worst-case running time, while Big Omega characterizes the best-case running time of an algorithm. There is not a one-to-one relationship between any of the cases and the asymptotic notations.

The following graph shows an example of functions $f(n)$ and $g(n)$ that have a Big Omega relationship.

A quick quiz

Did you know that if $f(n) \in O(g(n))$, then $g(n) \in \Omega(f(n))$? Try proving it!

Big ‘Theta’ - $\mathrm{\Theta }$