Computational Complexity

Scaling & Big-O Notation

Two algorithms solve the same problem, but one finishes instantly while the other takes centuries. Computational complexity measures how an algorithm's resource use—usually time (number of basic steps)—grows as input size $n$ grows.

We describe this growth using big-O notation, which captures the dominant term and drops constants and lower-order terms. For large $n$, only the fastest-growing part matters.

The Asymptotic Gulf

The gulf between complexity classes is enormous. For $n = 1{,}000{,}000$, a linear algorithm takes a million steps while a quadratic one takes a trillion—seconds versus weeks.

Big-O describes asymptotic behavior ($n \to \infty$), so $O(n)$ and $O(100n)$ are the same class. Choosing the right algorithm matters far more than machine speed.

Common pitfall: Confusing an algorithm's complexity class (its scaling trend) with its raw speed on small inputs. Big-O drops constants. A quadratic algorithm might beat a linear one on tiny inputs, but $O(n)$ is guaranteed to win once $n$ is large enough.