home

# 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$$