Amortized Analysis for Students — Simple Ideas and Python Examples

Why should you care?

When you hear O(1) amortized for appending to a Python list, it means:

• Most appends are very cheap.
• Occasionally one append is expensive because the list must grow (copy elements to a bigger block of memory).
• If you spread that rare “big cost” over many cheap appends, each append still looks like O(1) in the long run.

That “long run average” idea is amortized analysis.

---

Worst case vs amortized (coffee shop analogy)

Imagine a coffee stamp card: buy 9 coffees, the 10th is free.

• On the 10th visit you pay nothing extra for the reward — feels like a “big win” that day.
• Across 10 visits you paid for 9 drinks and got 10 servings of coffee.

So per drink, you paid a little less than full price on average.

Amortized view: one “expensive” bookkeeping moment (the free drink) is paid for by many cheaper visits before it.

In algorithms, one slow operation is often paid for by many fast operations that came before it.

---

Aggregate method (add all costs, divide by n)

A simple way students use:

1. Run n operations (for example, n appends).
2. Add up the total real work (basic steps / copies).
3. Divide by n → average cost per operation.

If that average is O(1), we say each operation is O(1) amortized.

This does not say every step is O(1) worst case — only that the average over many steps is constant.

---

Example 1 — Dynamic array: doubling capacity

Many languages grow arrays by doubling size when full. After a resize, there is room for many cheap appends before the next resize.

class GrowableArray:
    """Tiny toy model: not as fast as Python's real list, but shows the idea."""

    def __init__(self):
        self._data = [None] * 1  # start capacity 1
        self._size = 0

    def __len__(self):
        return self._size

    def append(self, value: int) -> None:
        if self._size == len(self._data):
            self._resize()
        self._data[self._size] = value
        self._size += 1

    def _resize(self) -> None:
        old = self._data
        new_cap = max(1, len(old) * 2)
        self._data = [None] * new_cap
        for i in range(self._size):
            self._data[i] = old[i]


def total_append_steps(n: int) -> int:
    """Rough step count: each append is 1 write; resize copies all existing items."""
    a = GrowableArray()
    steps = 0
    for k in range(n):
        before = len(a._data)
        if a._size == before:
            steps += a._size  # copies during resize (model)
        a.append(k)
        steps += 1  # place new element
    return steps


# Try it: total work grows ~ O(n), so average per append ~ O(1)
for n in (10, 100, 1000):
    s = total_append_steps(n)
    print(n, "appends ->", s, "steps, average", s / n)

Reading the numbers: total steps stay linear in n, so average per append stays bounded by a constant as n grows — that is O(1) amortized append.

---

Example 2 — Binary counter (increment amortized O(1))

Incrementing a binary number can flip many bits (all 1s roll over), but those “long carries” are rare.

def increment(bits: list[int]) -> int:
    """bits[0] is LSB. Returns number of bit flips."""
    flips = 0
    i = 0
    while i < len(bits) and bits[i] == 1:
        bits[i] = 0
        flips += 1
        i += 1
    if i < len(bits):
        bits[i] = 1
        flips += 1
    else:
        bits.append(1)
        flips += 1
    return flips


def run_counter(n: int) -> None:
    bits = [0]
    total_flips = 0
    for step in range(n):
        f = increment(bits)
        total_flips += f
    print(n, "increments ->", total_flips, "flips, average", total_flips / n)


run_counter(256)

Intuition: each bit flips from 0→1 once between resets; a reset 1→0 was “prepaid” by an earlier 0→1. Over many increments, total flips ≈ O(n), so amortized O(1) per increment.

---

Example 3 — Stack with “multipop” (optional stretch)

Sometimes an API has an operation that can be costly in one call, but costly calls remove many items that were paid for when they were pushed.

class Stack:
    def __init__(self):
        self._items: list[int] = []

    def push(self, x: int) -> None:
        self._items.append(x)

    def multipop(self, k: int) -> int:
        """Pop up to k items; returns how many pops happened."""
        count = 0
        while self._items and count < k:
            self._items.pop()
            count += 1
        return count

If you analyze any mix of n pushes and multipops on a stack that never holds more than n items total, total real pops cannot exceed total pushes. That is another “aggregate” style argument.

---

What amortized analysis is not

• It is not the same as average case over random inputs (that uses probability).
• It is not hiding worst cases: we still reason about real costs over a sequence of operations.

---

How to explain it in an interview (student version)

“Some operations rarely pay a large bill. If that bill grows linearly with how many cheap operations happened since the last bill, then per cheap operation we only pay a constant share on average — so the amortized cost is O(1).”

---

Key takeaways

• Amortized = spread a rare expensive step over many cheap steps.
• Dynamic arrays use doubling so resizes are rare enough → O(1) amortized append.
• Binary counter increments flip many bits only sometimes → still O(1) amortized per increment.
• Use the aggregate method early: sum real costs for n ops, divide by n.

---

Mini practice (Python)

1. Modify total_append_steps to print how many resize events happen for n = 1_000_000 (should be about log₂(n)).
2. For the binary counter, start from all zeros and run run_counter(10_000). Watch how the average flips per step stays small.

When you are comfortable here, revisit time complexity for individual worst-case operations, then compare with amortized guarantees for sequences — that contrast is what interviewers like to hear.