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