Some operations are usually fast but occasionally very slow. Reporting the worst-case cost of the slow operation would be misleading. Amortized analysis spreads the total cost across all operations to find the true average cost per operation over a sequence.
The Dynamic Array Example
A Python list (or Java ArrayList) is backed by a fixed-size array in memory. When you append an item:
- Normal case: There's room in the backing array. Copy the reference. $O(1)$.
- Full array case: The backing array is full. Allocate a new array of double the size, copy all N existing elements, then add the new item. $O(N)$.
At first glance, appending seems $O(N)$ in the worst case. But how often does resizing happen?
| Append # | Backing Array Size | Resize? |
|---|---|---|
| 1 | 1 → 2 | Yes |
| 2 | 2 → 4 | Yes |
| 3 | 4 | No |
| 4 | 4 → 8 | Yes |
| 5–8 | 8 | No |
| 9 | 8 → 16 | Yes |
Resizes happen at sizes 1, 2, 4, 8, 16... — powers of 2. The total copy work for N appends is $1 + 2 + 4 + ... + N = 2N$. Spread across N appends, that's $2N / N = 2$ copies per append on average. Dropping the constant: amortized $O(1)$ per append.
The Rent Analogy
If you pay $1,200 rent once a year, or $100 rent every month, the amortized cost is $100/month. The occasional large payment is real, but when averaged over time, the per-unit cost is constant. Similarly, the occasional $O(N)$ resize is real, but amortized over N appends, the per-append cost is $O(1)$.
Why this matters in interviews: If asked "what's the complexity of appending to a Python list?", the correct answer is "amortized $O(1)$." Saying just "$O(1)$" is slightly imprecise; saying "$O(N)$" is wrong in practice. Demonstrating you know the distinction signals senior-level understanding.