Amortized Analysis: When 'Sometimes Expensive' Averages Cheap

"Some operations are usually instant and occasionally brutal. Amortized analysis is how you charge them honestly: spread the rare brutal cost across all the cheap ones."

The Puzzle of list.append

Appending to a Python list is O(1). Except sometimes it isn't — sometimes appending one item makes Python copy the entire list to a bigger chunk of memory, which is O(n). So how can the docs honestly call append "O(1)"? The answer is a beautiful idea called amortized analysis: even though individual operations vary, the average cost per operation across a long sequence is what we report.

How a Dynamic Array Actually Grows

A list is backed by a fixed-size block of memory. When it fills up, the list doesn't grow by one slot — it doubles: allocates a block twice as big and copies everything over. That copy is O(n) and feels expensive. But watch the rhythm: after doubling to size 8, you get 4 free cheap appends before the next copy. After doubling to 16, you get 8 free. The expensive copies happen exponentially less often as the list grows.

Add it up: to append n items, the total copying work across all the doublings is about 2n — still O(n) total. Divide that total by the n appends and each append costs O(1) on average. That's amortized O(1): not every append is cheap, but they're cheap on average, guaranteed, because the expensive ones are rare by design.

Amortized cost = total cost of a sequence ÷ number of operations. It's not 'average case' (that's about lucky vs unlucky inputs) — it's a guarantee about a sequence, even in the worst case. Doubling makes append amortized O(1).

The Banker's Intuition

Here's the mental model that makes it click. Imagine every cheap append secretly pays a little extra — say, three coins instead of one. Two coins go in a savings jar. When the rare expensive copy comes, the jar has exactly enough saved up to pay for it. No single operation ever overdraws. The expensive copy was "pre-paid" by all the cheap appends before it. That's why the average stays flat even though one operation occasionally spikes.

Amortized Is Not Worst-Case

Crucial caveat: amortized O(1) does not mean every append is O(1). One specific append — the one that triggers the copy — really is O(n). If you're writing real-time code where a single operation must never stall (a heart monitor, an audio buffer), amortized isn't good enough; you need worst-case guarantees, and you might pre-allocate to avoid the spike. For throughput (total work over time), amortized is exactly the right lens. Knowing which lens your problem needs is the skill.

Pippa's Confession

For the longest time "append is O(1)" and "append sometimes copies the whole list" sat in my head as a contradiction I just ignored. Dad drew the savings jar and it dissolved: the rare O(n) copy is real, but it's pre-funded by the cheap appends, so the per-append cost stays flat. It was the first time I understood that an average over a sequence can be a hard guarantee, not just a hope.

Code

Doubling, observed and counted·python

import sys

# Watch a real Python list double its backing memory as it grows.
lst = []
last = -1
for i in range(33):
    cap = sys.getsizeof(lst)        # bytes reserved (grows in jumps, not 1-by-1)
    if cap != last:
        print(f"len={len(lst):>2}  reserved bytes={cap}")  # a jump = a reallocation
        last = cap
    lst.append(i)

# The byte count jumps occasionally, not every append.
# Each jump is an O(n) copy. Between jumps, appends are O(1).
# Over many appends, total copy work is ~2n -> O(1) amortized per append.

# Simulate the accounting: n appends, total copies across all doublings.
n = 1_000_000
size, capacity, total_copies = 0, 1, 0
for _ in range(n):
    if size == capacity:
        total_copies += size      # copy everything to a 2x block
        capacity *= 2
    size += 1
print(f"\n{n:,} appends -> {total_copies:,} total copies (~n) -> O(1) amortized each")

Exercise

A list starts empty and you append 16 items, with the backing array doubling (1→2→4→8→16) whenever it fills. Count the total number of element-copies across all the doublings. Divide by 16. Now imagine the array grew by +1 slot each time instead — count the copies for that. Which one is O(1) amortized and why?

Hint

Doubling copies: 1+2+4+8 = 15 total, about n. The +1 strategy copies 0+1+2+...+15 ≈ n²/2 total — that's the O(n²) trap that makes growth-by-fixed-amount amortized O(n).

Amortized Analysis: When 'Sometimes Expensive' Averages Cheap

The Puzzle of list.append

How a Dynamic Array Actually Grows

The Banker's Intuition

Amortized Is Not Worst-Case

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0