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 keeps spare capacity beyond its current length. When that space runs out, it allocates a larger block and moves the existing references, an O(n) event. The important invariant is geometric growth with spare capacity, not an exact doubling rule. CPython's precise growth factor is an implementation detail that can vary by version.

For a model that clicks, pretend capacity doubles. After growing to 8 slots, as many as 4 cheap appends arrive before the next copy; at 16 slots, as many as 8. The moved-element total is 1+2+4+…, less than 2n after n appends. That makes total copying O(n) and append amortized O(1). This is a teaching model, not a promise that CPython doubles exactly. The real invariant is geometric growth that puts many cheap appends between expensive copies.

Amortized cost divides the total cost of an operation sequence across its operations. It is different from average-case analysis over an input distribution. Geometric capacity growth is what gives dynamic-array append its amortized O(1) bound.

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

Observed spare capacity and a geometric-growth model·python

import sys

# Watch a Python list's reserved memory grow in occasional jumps.
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 one simple doubling model; CPython's actual factor is version-specific.
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).

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