Amortized Analysis: Why "Usually Fast" Is Good Enough

Concepts covered: List Modification

Sometimes an operation is fast most of the time but occasionally very slow. Your instinct might be to judge the algorithm by its worst moment. Amortized analysis offers a smarter perspective: spread the total cost evenly across all operations. If the occasional slow operation is rare enough, the average cost per operation can still be very low.

The Real Cost of list.append()

Every Python developer uses list.append() without thinking twice. But under the hood, something surprising happens. A Python list stores its elements in a contiguous block of memory. When that block is full and you append one more item, Python must allocate a bigger block and copy everything over. That single append touches every element in the list.

So is append O(1) or O(n)? The answer is: it depends on which append you are looking at. Most appends are O(1) because there is room in the current block. But the occasional resize is O(n) because Python copies all existing elements. If you only looked at the worst case, you would say append is O(n). That would be misleading, because that expensive resize happens very rarely.

The Key Insight: Spreading the Cost

Here is the trick. Python does not just add a little bit of extra space when it resizes. It roughly doubles the capacity. That means after a resize, you get to do many cheap O(1) appends before the next resize happens. The expensive operation "pays for itself" because it buys you a long run of cheap operations.

Think of it like a jar of coins. Every time you append, you put in 3 coins. One coin pays for the actual append. The other 2 coins go into the jar. When a resize happens (say, copying 1,000 elements), the jar has accumulated at least 1,000 coins to pay for it. The jar never goes empty. So even though individual operations vary wildly in cost, the average cost per operation stays constant. That is what amortized O(1) means.

# Watch Python list resizing in action
import sys

sizes = []
my_list = []
prev_size = sys.getsizeof(my_list)

for i in range(80):
    my_list.append(i)
    current_size = sys.getsizeof(my_list)
    if current_size != prev_size:
        sizes.append((i, current_size, current_size - prev_size))
        prev_size = current_size

print("Resize events (element #, new bytes, jump):")
for elem, total, jump in sizes:
    print(f"  After element {elem:>2}: {total:>4} bytes (+{jump})")

print(f"\nTotal appends: 80")
print(f"Resize events: {len(sizes)}")
print(f"Most appends were free (no resize).")

Output:

Resize events (element #, new bytes, jump):
  After element  0:   88 bytes (+32)
  After element  4:  120 bytes (+32)
  After element  8:  184 bytes (+64)
  After element 16:  248 bytes (+64)
  After element 24:  312 bytes (+64)
  After element 32:  376 bytes (+64)
  After element 40:  472 bytes (+96)
  After element 52:  568 bytes (+96)
  After element 64:  664 bytes (+96)
  After element 76:  792 bytes (+128)

Total appends: 80
Resize events: 10
Most appends were free (no resize).

Out of 80 appends, only 10 triggered a resize. The other 70 were instant. If you measured just the worst single append, you would see O(n) cost. But if you measured the total cost of all 80 appends combined, it would be close to 80 units of work (not 80 times n). That is amortized O(1).

Where Amortized Analysis Shows Up

Amortized analysis is not just an academic concept. It explains the performance of many tools you use every day:

Python list.append(): Amortized O(1). The doubling strategy means resizes are rare enough that the average cost stays constant.
Hash table resizing: Python dicts and sets resize when they get too full. Same doubling strategy, same amortized O(1) for inserts.
StringBuilder / StringIO: Dynamic buffer gives amortized O(1) per character. Naive string concatenation is O(n).
Database auto-vacuuming: PostgreSQL periodically reclaims space from deleted rows. The cleanup cost is amortized across many fast operations.

Amortized vs Average Case

These two ideas sound similar but they are fundamentally different. Average case assumes your inputs are random and calculates the expected runtime over all possible inputs. Amortized analysis makes no assumptions about inputs. It looks at any sequence of operations and guarantees that the total cost is bounded. Average case is about typical luck. Amortized analysis is a guarantee that holds for every possible sequence.

About this lesson

This section is part of the Complexity: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.