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 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) with a Big Omega relationship.

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