Other Common Asymptotic Notations and Why Big O Trumps Them

Learn about the various asymptotic notations for algorithms and why computer scientists prefer Big O over other notations.

Big Omega: Ω(.)\Omega(.)

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

Note: It is a common misconception that Big O characterizes the 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 f(n)f(n) and g(n)g(n) that have a Big Omega relationship:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.