Other Common Asymptotic Notations and Why Big O Trumps Them
Big ‘Omega’ -
Mathematically, a function is in if there exists a real constant and there exists such that for . In other words, for sufficiently large values of , will grow at least as fast as .
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 no one-to-one relationship between any of the cases and the asymptotic notations.
The following graph shows an example of functions and that have a Big Omega relationship.