Big O notation

When expressing the Computational complexity of algorithms, big O notation is used to classify their behaviour as the size of inputs tends towards some particular value or infinity.

Formally \(f\) may be said to be \(O(g)\), or \(f(n) = O(g(n))\) as \(n \to \infty\) when \[ |f(n)| \leq c \cdot g(n) \quad \forall n \ge k \] where \(c\) and \(k\) are called the witnesses to the relation.

As a concrete example, consider \(3n^{2} + 4n = O(n^2)\). As \(n \le n^2\) for all \(n \ge 1\), we may infer that \(3n^{2} + 4n \le 3n^{2} + 4n^{2}\), which implies \(3n^{2} + 4n \le 7n^{2}\). This shows the relations to hold for witness of \(c = 7\) and \(k = 1\).

Common orders

Notation Term
\(O(1)\) constant
\(O(\log \log n)\) double logarithmic
\(O(\log n)\) logarithmic
\(O(n^{c}) \text{ where } 0<c<1\) fractional power
\(O(n)\) linear
\(O(n \log n)\) linearithmic
\(O(n^2)\) quadtratic
\(O(n^c)\) polynomial
\(O(c^{n}) \text{ where } c>1\) exponential
\(O(n!)\) factorial

While \(O(g)\) is used to denote \(f \leq g\) other common symbolism exists for similar relations.

Notation Comparison Limit Definition
\(f = o(g)\) \(f < g\) \(\lim_{x \to \infty} \frac{f(x)}{g(x)} = 0\)
\(f = O(g)\) \(f \le g\) \(\lim_{x \to \infty} \frac{f(x)}{g(x)} < \infty\)
\(f = \Theta(g)\) \(f = g\) \(\lim_{x \to \infty} \frac{f(x)}{g(x)} \in \mathbb R_{>0}\)
\(f = \Omega(g)\) \(f \ge g\) \(\lim_{x \to \infty} \frac{f(x)}{g(x)} > 0\)
\(f = \omega(g)\) \(f > g\) \(\lim_{x \to \infty} \frac{f(x)}{g(x)} = \infty\)