Complexity Analysis

Measuring Cost Precisely

Complexity analysis predicts how an algorithm's time (operations) and space (memory) grow with input size $n$ without running code.

The tool is asymptotic notation, which ignores constants and lower-order terms to focus on scaling behavior for large inputs:

Count dominant operations: a loop is $O(n)$, nested loops are $O(n^2)$, halving is $O(\log n)$, and fixed work is $O(1)$.

Common pitfall: Writing '$O(3n^2 + 5n)$'. Drop constants and lower terms: it is simply $O(n^2)$, because the dominant term alone captures scale.

Cases and Space

Costs depend heavily on case: the worst case bounds maximum slowness, the average case reflects typical inputs, and the best case is usually uninformative.

Space complexity measures memory. Algorithms often feature a space-time trade-off: merge sort takes $O(n \log n)$ time but $O(n)$ extra space, while heapsort sorts in place with $O(1)$ space.

Quick Rules:

• Only the fastest-growing term matters: $O(n^2 + n)$ simplifies to $O(n^2)$.
• Quicksort is $O(n \log n)$ average but $O(n^2)$ worst case.
• Always evaluate both time and memory constraints before selecting an algorithm for large datasets.