Big O notation

Big O notation is denoted with \(O(g(n))\) and indicates an worst-case asymptotic upper bound. While \(2n^2\) is in \(O(n^9)\), it’s preferred to be as precise as possible and state the lowest valid case: \(2n^2 = O(n^2)\).

Little-o notation

Little-o notation, written as \(o(g(n))\), is a stronger statement than Big O notation. It implies that \(g(x)\) grows much faster than \(f(x)\). It’s defined as:

\[f(x) = o(g(x)) \overset{\Delta}{=} \lim_{x \to \infty} \frac{f(x)}{g(x)} = 0\]

Relationship with Big O notation

\[\begin{align}3n^3 &= O(n^3) \\ 3n^3 &\ne o(n^3) \\ 3n^3 &= o(n^4)\end{align}\]

To use an analogy:

\[\begin{align}f(n) &= O(g(n)) &\approx a &\le b \\ f(n) &= o(g(n)) &\approx a &< b\end{align}\]

Big Omega notation

Big Omega notation, written as \(\Omega(g(n))\), indicates an worst-case asymptotic lower bound. While \(2n^2\) is in \(\Omega(1)\), it’s preferred to be as precise as possible and state the lowest valid case: \(2n^2 = \Omega(n^2)\).

Big Theta notation

Big Theta notation, written as \(\Theta(g(n))\), indicates \(f\) is bound above and below, asymptotically, by \(g\) (a tight bound).

\[\Theta(n) \implies O(n) \;\text{and}\; \Omega(n)\]

References