Big O Notation

A precise guide to asymptotic upper bounds, comparison rules, proofs, and the limits of Big O claims.

Big O compares long-run growth rates rather than exact running times. Constant, logarithmic, linear, quadratic, and exponential curves share an input-size axis. Their increasing separation shows why dominant growth matters as input becomes large.

Precise definition

For eventually non-negative functions $f$ and $g$, the statement $f(n)=O(g(n))$ means there exist constants $c>0$ and $n_0$ such that $0\le f(n)\le c g(n)$ for every $n\ge n_0$. Big O is an asymptotic upper bound, not automatically a tight bound or an equality of functions.

Notation and mathematical language

Use $O(g)$ for an upper bound, $\Omega(g)$ for a lower bound, and $\Theta(g)$ when both hold. The variable $n$ must denote a specified input size. Constants $c$ and $n_0$ are witnesses in a proof; they may depend on the functions but not on $n$.

Conceptual picture

Asymptotic notation deliberately ignores fixed multiplicative factors and finite initial behaviour. It answers how resource use scales when inputs grow, not exactly how long a particular machine takes. Thus $3n^2+10n+7$ and $n^2$ share a quadratic growth class even though their measured times differ.

Fully worked example

Interpretation and application

Complexity classes guide algorithm selection: replacing a quadratic scan with an $n\log n$ method can dominate hardware improvements at large scale. Constants and cache effects still matter for practical sizes, so an asymptotic comparison should accompany, not replace, measurement on representative inputs.