Big-O Notation

Big-O notation describes the upper bound on the growth rate of a function. When we say an algorithm runs in $O(n)$ time, we mean that as the input size $n$ grows large, the number of operations is bounded above by a constant times $n$. We deliberately ignore constant factors and lower-order terms because they become negligible at scale.

Why we use it

Algorithms that look fast on small inputs can be catastrophically slow at scale. A function that visits every pair of $n$ items does $\Theta(n^2)$ work; at $n = 10^6$ that is $10^{12}$ operations — roughly an hour on a fast CPU. Compare this to $O(n \log n)$, which finishes the same input in seconds.

Formal definition

We write $f(n) = O(g(n))$ when there exist positive constants $c$ and $n_0$ such that for all $n \geq n_0$, $|f(n)| \leq c \cdot g(n)$. The notation captures an asymptotic ceiling — actual runtime can be lower for any fixed input.

Reading Big-O in practice

When you see $O(n^2 + n)$ written, treat it as $O(n^2)$ — only the dominant term matters. Coefficients are dropped: $O(5n)$ is just $O(n)$. Logarithms of any constant base collapse to the same class because they differ only by a multiplicative constant.

Variants

$O$, $\Omega$, and $\Theta$ describe upper, lower, and tight bounds respectively. In casual interview talk people use "Big-O" to mean "tight bound" even though formally that's $\Theta$.