Best, Worst, Average and Amortized
"Hash lookup is O(1)" and "appending to a list is O(1)" are both true, and both hide something. The first is an average, and an attacker can turn it into O(n). The second is an amortized figure, and it includes the occasional append that copies the entire list. A cost can be stated four ways, and the one that pages someone at night is rarely the one in the documentation.
The four are best case, worst case, average case and amortized, and each is a legitimate claim about the same code. They answer different questions, and mixing them up is how a service with excellent average numbers falls over on one request.
One Algorithm, Several Costs
Search an unsorted list for a value. If the value happens to be first, the search takes one step: that is the best case. If it is last, or missing, the search reads all n items: that is the worst case. Over many searches for values spread evenly through the list, it reads about half the list on average, n over 2, which is still O(n).
The best case is almost never useful, because it describes the luckiest input and promises nothing. The worst case is a guarantee: no input can make the code slower. The average needs an assumption about which inputs will arrive, and it is only as good as that assumption.
The Average Is an Assumption
Quicksort averages n log n comparisons on randomly ordered input and degrades to n² on input it handles badly, which Chapter 7 shows. A hash table averages about one probe per lookup only if its keys spread evenly across its slots. Both averages are true, for the inputs they assume.
Real inputs are not random. They arrive already sorted, heavily repeated, or deliberately chosen. An average stated for random data says nothing about data that arrives in order, and nothing at all about data picked by someone who has read the same textbook.
Amortized: Paying in Advance
A Python list keeps spare capacity at the end. Most appends write one slot and return. When the spare capacity runs out, the list allocates a larger block of memory and copies every existing element into it, and that one append costs as much as the whole list.
The trick is that the capacity grows by a proportion of the current size, not by a fixed amount. CPython grows a list by about an eighth plus a few slots; many other languages double. Because each growth adds room proportional to what is already there, the expensive copies get rarer as the list gets longer, and the total cost of n appends stays a constant multiple of n. Divided by n, that is O(1) per append, which is what "amortized O(1)" means.
The chart shows the first 80 appends to an empty list under CPython's rule. The short bars are single writes. The tall bars are the appends that found the list full and copied it. The dashed line is the running average, which stays low while the spikes grow. Over millions of appends CPython's modest growth copies each element about eight or nine times in total. That is still a constant, and it is CPython's trade: less wasted memory at the end of every list in exchange for more copying. A list that doubled would copy each element about once or twice and leave up to half its block empty.
The Worst Case an Attacker Picks
When input comes from outside, the worst case is not unlikely. It is one request away. Keys crafted to collide in a hash table turn constant-time inserts into linear-time ones, so parsing one form submission full of such keys costs tens of seconds to minutes of CPU. A naive quicksort that always picks the first element as its pivot does its worst on input that is already sorted. A regular expression with nested repetition backtracks exponentially on a string built to make it fail.
There are two defences. Choose a structure whose worst case is acceptable, or add randomness the attacker cannot predict. Python took the second route for strings: since Python 3.3 string hashing is randomized per process by default, precisely because crafted collisions made the average case irrelevant. Chapter 5 shows how the attack works.
Amortized Is Not Every Call
An amortized O(1) append still includes the one append that has to move ten million pointers, 80 megabytes. When the allocator cannot grow the block where it stands, that append takes milliseconds, while the one before it took nanoseconds. A hash table that resizes, a garbage collection cycle and a log rotation have the same shape: cheap on average, occasionally expensive. The expensive call lands on one unlucky request, and that request has the same deadline as all the others.
Where the Cases Show Up in Production
A service's median latency is the average case. Its 99th-percentile latency is where amortized spikes and bad inputs live. Its outage is the worst case that someone found. A service with average O(1) behaviour and an exploitable O(n) worst case is one crafted request away from its slowest behaviour, which is why latency percentiles and limits on input size matter more than any average.
Average case is the expected cost of one operation over a distribution of inputs. It is wrong when the inputs are not what was assumed, and any single operation can still hit the worst case. Hash lookups are average-case O(1).
Amortized is the guaranteed total cost of a sequence of operations, divided by their number. It assumes nothing about the input, but one operation in the sequence can still be expensive. List appends are amortized O(1).
- "Amortized O(1) means every append is fast." The total is O(n), but one append in the sequence copies the whole list. In a latency-sensitive loop that one call is the spike on the graph.
- "The average case is what I will see." Only if the inputs match the assumed distribution. Data that arrives already sorted, heavily repeated or crafted by an attacker lands on the worst case far more often than chance would predict.
- "The worst case is too pessimistic to care about." On any path that takes outside input, the worst case is chosen, not suffered. Python randomized string hashing because crafted collisions were a working attack.
- "Growing by a fixed amount is as good as growing by a multiple." Adding a hundred slots at a time makes n appends cost O(n²) in total, because every growth copies everything again. Only proportional growth gives amortized O(1).
- "The best case is a useful selling point." Every search is O(1) when the item happens to be first. A best-case figure describes the luckiest input and guarantees nothing.
- Ask which case an O describes before relying on it. An average-case bound on a path an attacker controls is not a guarantee.
- Watch the 99th percentile and the maximum latency, not only the median. Amortized and worst-case costs never show up in an average.
- Preallocate, or build in one step, when the final size is known. It removes the growth copies and their spikes from the hot path.
- Bound or randomize anything an outsider can shape. Limits on input size, randomized hashing and randomized pivots take the worst case out of an attacker's hands.
Knowledge Check
Appending to a Python list is O(1) amortized, yet some appends copy the entire list. How can both be true?
- The copying happens on a background thread, so the append itself never waits for it
- Capacity grows by a proportion, so the total copying over n appends stays proportional to n
- Copying pointers is so cheap that it counts as a single step whatever the list's length
- Python lists never reallocate; they link fixed-size blocks together as they grow longer
What is the difference between an average-case bound and an amortized bound?
- They mean the same thing; amortized is simply the older name for average
- Amortized assumes random input; average guarantees the total of a sequence
- Average assumes an input distribution; amortized guarantees a sequence total
- Average is always a tighter bound than amortized for the same data structure
A list implementation grows its capacity by a fixed 100 slots whenever it is full. What is the total cost of n appends?
- O(n), the same as doubling, since each append is cheap
- O(n²), because every fixed growth copies everything again
- O(n log n), because the copies happen at halving intervals
- O(1) in total, because 100 slots absorb the growth cost
A service's median latency is 4 milliseconds, but its 99th percentile is 180 milliseconds. Which explanation fits the pattern best?
- The network is slow for every request, so every response arrives late
- The algorithm's average case is poor, so most requests take too long
- Rare expensive operations, such as resizes or bad inputs, hit a few requests
- Every request is slow, and the median simply hides how slow they all are
You got correct