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 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 best-case running time of an algorithm. There is no 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.

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

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

if $f$ ...