Other Common Asymptotic Notations and Why Big (O) Trumps Them

This lesson covers the various asymptotic notations for algorithms and why computer scientists prefer Big (O) instead of 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).

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.