Best, Worst, & Average Case
Three Ways to Measure an Algorithm
Every algorithm's cost depends on its input. Two inputs of the same size can produce wildly different runtimes. Complexity analysis formalizes three perspectives on that variation.
Best case — Ω (Omega): the input that makes the algorithm finish fastest. For linear search over a list of N items: Ω(1) — the target occupies the first position. One comparison, done.
Worst case — O (Big O): the input that makes the algorithm finish slowest. For linear search: O(N) — the target sits last in the list, or does not appear at all. Every element requires inspection.
Average case — Θ (Theta): expected cost over all possible inputs, assuming uniform distribution. For linear search with the target equally likely to occupy any of N positions: Θ(N/2) = Θ(N). The constant 1/2 drops because Theta expresses tight asymptotic growth, not exact coefficients.
Why Worst Case Dominates
Systems must handle the worst case. A database query that averages 10 ms but occasionally takes 60 seconds produces a user-visible failure. Engineers design for worst-case bounds so that performance stays predictable regardless of input. Average-case analysis has value in probabilistic settings, but worst-case analysis gives guarantees.
Binary Search Case Analysis
Binary search works only on sorted arrays. At each step: compare the target to the element at the midpoint. If the target equals the midpoint, return it. If the target is smaller, recurse on the left half. If larger, recurse on the right half.
Each comparison eliminates half of the remaining candidates.
Memory Growth & Time-Space Tradeoffs
Counting Memory, Not Operations
Time complexity measures the number of operations an algorithm executes. Space complexity measures the extra memory it allocates beyond its input. Both matter in production systems: a fast algorithm that allocates O(N²) memory will exhaust a server.
O(1) space: constant extra memory regardless of N. An in-place sort (e.g. insertion sort) swaps elements inside the original array. It uses a handful of temporary variables — O(1) no matter how large the array.
O(N) space: memory proportional to input size. Creating a copy of an N-element array requires N slots. Building a hash set from a list of N strings stores up to N entries.
O(N²) space: memory proportional to N². Building an N×N adjacency matrix for a graph with N vertices requires N² cells. At N = 10,000 vertices, that is 10^8 entries — hundreds of megabytes for a simple boolean grid.
Time-Space Tradeoffs
One of the fundamental moves in algorithm design: trade space for time, or time for space.
Hash tables use O(N) extra space to achieve O(1) lookup. Without the hash table, a scan over a list achieves O(N) lookup with O(1) extra space. The hash table pays memory to buy speed.
Memoization stores previously computed results (O(N) or more space) to avoid recomputing them. Recursive Fibonacci without memoization runs in O(2^N) time. With memoization: O(N) time and O(N) space. The space investment shrinks time exponentially.
Hash Dictionary vs Sorted List
Compare two strategies for counting word occurrences in a document of N words:
Strategy A: a dictionary (hash map). Insert each word; increment its count.
Strategy B: maintain a sorted list of seen words; use binary search to check membership before inserting.
Amortized Analysis: Spreading the Cost
When Occasional Expense Does Not Ruin Average Performance
Some operations are occasionally expensive but cheap on average across a sequence. Amortized analysis computes the average cost per operation over the entire sequence — not the worst-case cost of a single operation.
Dynamic array (Python list, Java ArrayList): starts at capacity 1. When full, doubles capacity. Doubling copies all existing elements: O(N) work for one append. But doublings are rare. After N total appends, how many total copy operations occurred?
Doublings happen at sizes 1, 2, 4, 8, ..., N/2. Copy counts: 1 + 2 + 4 + ... + N/2. This is a geometric series summing to N − 1 total copies across all N appends. Average copies per append: (N − 1) / N < 1, so O(1) amortized per append despite O(N) worst-case cost per doubling.
Why Amortized Analysis Matters
A system that occasionally pauses to resize, rebalance, or compact a structure may appear to have alarming worst-case individual operations. Amortized analysis reveals that the alarm is false: the rare expensive events get paid for by the many cheap ones. Understanding amortized cost prevents over-engineering: adding complexity to avoid a rare O(N) operation that contributes only O(1) amortized is wasted work.
Going deeper: The unhamming course applies complexity analysis to real-world defects in production software. See [The Missing Chapter: Algorithmic Complexity](/en/un/unhamming_algorithmic_complexity) & [MOAD-0001: The Sedimentary Defect](/en/un/unhamming_moad_sedimentary).
Hash Table Amortized Insert
A hash table starts empty and doubles capacity whenever load factor exceeds 0.75. Inserting 1,000 elements triggers exactly 10 doublings at capacities 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.