ZERO / HERO
The occasional big shop

Amortised Analysis

The analogy

Most days you grab milk on the way home — quick. Once a month you do an enormous shop that eats an afternoon. Averaged across the month your shopping is cheap. Amortised cost is that average, and it is the honest number for things like growing an array.

Visualizer

The occasional big shop

step 1 / 9
n = 64steps (log scale)

Append 1: one write. Cheap.1 appends, 0 resizes — running average 1.00 writes/append

a = []
for i in range(24):
    a.append(i)      # usually 1 write
                     # occasionally copies everything

import sys
sys.getsizeof(a)     # jumps at each resize
# amortised O(1) per append
Check yourself

Amortised O(1) means…