Complexity and Performance Trade-offs

How an Algorithm Scales

Two programs can both be correct yet differ wildly in speed as data grows. Complexity analysis measures how an algorithm's cost grows with input size $n$, ignoring hardware constants to focus on the growth shape.

Big-O notation expresses an upper bound on that growth. For large $n$, growth classes dominate all constants; an $O(n \log n)$ sort beats $O(n^2)$ regardless of tuning.

Trade-offs and Pitfalls

Performance involves choices beyond raw loops. The space-time trade-off lets you spend more memory to save time, such as using a lookup table.

An algorithm also has best, average, and worst cases. Big-O usually describes the worst case unless specified otherwise.

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

Common pitfall: Judging performance on small inputs where constant factors dominate. An $O(n^2)$ algorithm can beat an $O(n \log n)$ one on tiny inputs, yet lose catastrophically as $n$ scales.