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)\]