Complexity and Performance Trade-offs

How an Algorithm Scales

Two programs can both be correct yet differ enormously in speed as the input grows. Complexity analysis measures how an algorithm's cost — usually time or memory — grows as a function of the input size $n$, ignoring hardware-specific constants and focusing on the growth shape.

Big-O notation expresses an upper bound on that growth. Common classes, from best to worst:

The point of ignoring constants is that for large $n$, the growth class dominates everything else: an $O(n \log n)$ sort beats an $O(n^2)$ sort for large inputs no matter how cleverly the slow one is tuned. A nested loop over the same data is a classic $O(n^2)$ signal; halving the problem each step signals $O(\log n)$.

Complexity also captures trade-offs. Often you can spend more memory to save time (a lookup table), or vice versa — the space–time trade-off. And an algorithm's best, average, and worst case can differ; Big-O usually describes the worst case unless stated otherwise.

Common pitfall: judging performance by testing on small inputs, where constant factors dominate and an asymptotically worse algorithm may look fine or even faster. Complexity is about how cost grows as $n$ gets large; an $O(n^2)$ algorithm can beat an $O(n \log n)$ one on tiny inputs yet lose catastrophically as the data scales.

A cost-vs-n plot with an accent curve set for each of O(log n), O(n), O(n log n), O(n^2), diverging sharply as n grows to make the growth-class ranking unmistakable.

$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2)$$