Complexity Analysis

Measuring Cost Precisely

Complexity analysis determines how an algorithm's resource use — time (operations) and space (memory) — grows with input size $n$, so you can compare algorithms and predict scaling without running them.

The tool is asymptotic notation, which describes growth for large $n$, ignoring constants and lower-order terms:

• Big-O ($O$) is an upper bound: the algorithm grows at most this fast.
• Big-Omega ($\Omega$) is a lower bound: at least this fast.
• Big-Theta ($\Theta$) is a tight bound: both — the algorithm grows exactly this fast.

To analyze, count the dominant operations as a function of $n$: a single loop over the data is $O(n)$; a loop inside a loop is $O(n^2)$; halving each step is $O(\log n)$; and constant work regardless of $n$ is $O(1)$. Only the fastest-growing term matters: $O(n^2 + n)$ is just $O(n^2)$, because for large $n$ the $n^2$ term dominates.

Costs can differ by case. The worst case (the input that makes the algorithm slowest) is the usual guarantee — it bounds performance no matter what. The average case describes typical behavior over expected inputs (quicksort is $O(n \log n)$ average but $O(n^2)$ worst). The best case is often uninformative.

Do not forget space complexity: an algorithm may be fast but memory-hungry. Merge sort is $O(n \log n)$ time but needs $O(n)$ extra space to merge, while heapsort sorts in place with $O(1)$ extra — another space–time trade-off to weigh.

Common pitfall: keeping constant factors and lower-order terms in a Big-O answer, writing "$O(3n^2 + 5n + 7)$." Asymptotic analysis drops constants and lower-order terms: that is simply $O(n^2)$. The whole point is to compare growth shape, not exact operation counts — the dominant term alone captures how the algorithm scales.