Amortized Analysis

Python's list.append() is described as O(1) — but that can't be literally true for EVERY call, since occasionally the underlying array runs out of room and has to be resized, which means copying every existing element into a bigger array (an O(n) operation). Amortized analysis resolves this apparent contradiction: individual operations can occasionally be expensive, but the AVERAGE cost per operation, over a long sequence, is still O(1).

def total_resizes(n):
    capacity = 1
    size = 0
    resizes = 0
    for _ in range(n):
        if size == capacity:
            capacity *= 2
            resizes += 1
        size += 1
    return resizes

print(total_resizes(1000))   # far fewer than 1000 -- doubling grows capacity exponentially

Here's the key insight: because capacity DOUBLES each time (not just increases by a fixed amount), each resize copies roughly as many elements as ALL the previous resizes combined copied in total. Summing 1 + 2 + 4 + 8 + ... + n/2 (the sizes at each resize) totals just under 2n — proportional to n, not to the NUMBER of resizes.

def total_copy_operations(n):
    capacity = 1
    size = 0
    total_copies = 0
    for _ in range(n):
        if size == capacity:
            total_copies += capacity   # this resize's copying cost
            capacity *= 2
        size += 1
    return total_copies

Since the total copying work across n appends is O(n), the AVERAGE (amortized) cost per individual append is O(n)/n = O(1) — even though any single append might trigger an O(n) resize. This is why doubling (not adding a fixed amount) is the standard growth strategy for dynamic arrays — growing by a fixed amount instead would make resizes happen proportionally to n, making the amortized cost O(n), not O(1).