Amortized Analysis

A thousand appends

An array has a fixed number of slots, its capacity. A growable list hides that limit. When an append finds every slot taken, the list allocates a bigger array, copies every element across, and only then writes the new one. Throughout this module the cost is one unit per element written, removed or copied. Allocating the new block is charged nothing, because it is one call however big the block is.

There are two obvious ways to choose "bigger": add a few slots, or double. Start from capacity 1 and append a thousand elements:

• growing by 4 slots at a time costs 125,750 units;
• doubling costs 2,023.

Both rules have appends that copy the entire array, so a single append can be just as expensive under either. Yet one total is sixty times the other, and the gap keeps widening as the list grows. This module is about the kind of guarantee that tells them apart.

def append_costs(n, grow, cap=1):
    """Cost of each of n appends: 1 write, plus a copy of
    every element when the array is full."""
    costs, size = [], 0
    for _ in range(n):
        cost = 1
        if size == cap:
            cost += size          # copy everything into the new block
            cap = grow(cap)
        size += 1
        costs.append(cost)
    return costs

double = lambda cap: 2 * cap
plus4 = lambda cap: cap + 4

assert sum(append_costs(1000, plus4)) == 125_750
assert sum(append_costs(1000, double)) == 2_023

On a small scale the two rules look alike. Here are the first seventeen appends under each:

d17 = append_costs(17, double)
a17 = append_costs(17, plus4)
assert d17 == [1, 2, 3, 1, 5, 1, 1, 1, 9, 1, 1, 1, 1, 1, 1, 1, 17]
assert a17 == [1, 2, 1, 1, 1, 6, 1, 1, 1, 10, 1, 1, 1, 14, 1, 1, 1]
assert sum(d17) == 48 and sum(a17) == 45

Analysing one append at a time

The natural first analysis looks at one append in isolation. The worst append copies everything, which is up to $n-1$ elements, so $n$ appends cost $O(n^2)$. That is true under both rules.

For growth by a constant it is also the right answer. With $c$ new slots per resize, the resizes come every $c$ appends and copy $1,1+c,1+2c,\dots$ elements. That is an arithmetic series, and it sums to about $n^2/(2c)$. For $c=4$ and $n=1000$ this estimate gives 125,000 copies, and the exact count is 124,750. A bigger constant only divides the quadratic by $c$.

For doubling, the per-append bound is far too pessimistic. The analysis charges every append the price of the rarest one. After a doubling to capacity $2c$, the next expensive append is $c$ appends away, and the copy it makes is only as big as the number of appends since the one before. Expensive appends are paid for by the cheap appends between them. Making "paid for by" precise is what the rest of this module does.

The model: amortized cost

Three kinds of bound appear in this course, and they are easy to mix up:

An amortized bound involves no probability and no average over inputs. The sequence may be chosen by an adversary who knows the code. What it gives up is a guarantee for any one operation. The 1,025th append to a doubling array copies 1,024 elements, and the amortized bound does not say otherwise. It only says that someone has already paid for that copy.

Method 1: add it all up

The aggregate method bounds the total directly.

Theorem. $n$ appends to a doubling array that starts at capacity 1 cost less than $3n$.

Proof. There are $n$ writes. A copy happens when the array is full, at sizes $1,2,4,\dots ,2^j$, where $2^j\le n-1$. These copies total $1+2+\dots +2^j=2^{j+1}-1<2n$. Adding the writes gives less than $3n$. $◻$

On the seventeen appends above, the copies are $1+2+4+8+16=31$ and the total is $17+31=48\le 51$. The series here is geometric. Each copy is as large as all the earlier copies put together, so the last copy dominates the sum. The arithmetic series of the constant rule has no such term.

assert all(sum(append_costs(n, double)) < 3 * n for n in range(1, 2000))

The aggregate method needs a formula for the whole sequence. Once pops can come in any order between the appends, that formula is hard to write down. The next two methods reason about one operation at a time, and they still bound the total.

Method 2: prepay every append

The banker's method charges every operation a fixed price, which may be more than it costs. The surplus is saved as credits stored on the structure, and an expensive operation spends them. If no credit balance ever goes negative, the total actual cost is at most the total charged.

For doubling, charge 3 per append. One unit pays for the write, and two are stored on the new element. A resize spends one credit per element it copies, taking them from the newest elements first. Here is the array from capacity 1 after sixteen appends, just before append 17 doubles it:

Why it holds. A resize from capacity $c\ge 2$ happens when size reaches $c$. The previous resize happened when size was $c/2$, so $c/2$ elements have been appended since then, and they hold $c$ credits. That is exactly one credit per element to copy. After the copy they hold none, and the new array is half empty, ready for the next $c$ appends to fill it with $2c$ fresh credits. The very first resize, from capacity 1, has one element with 2 credits against a bill of 1, which is the leftover credit in the figure. The balance never goes negative, so $n$ appends cost at most $3n$.

bank = 3 * 16 - sum(d17[:16])   # charged minus spent, after 16 appends
assert bank == 17
assert d17[16] - 1 == 16         # the 17th append copies 16 elements

Method 3: a potential

Credits scattered over cells are awkward to track. The potential method replaces them with a single number $\Phi$ computed from the state of the structure. Define

$${\text{amortized}}_i={\text{actual}}_i+{\Phi }_i-{\Phi }_{i-1}.$$

Adding up over $k$ operations, the middle terms cancel (the sum telescopes):

$$\sum _{i=1}^k{\text{actual}}_i=\sum _{i=1}^k{\text{amortized}}_i+{\Phi }_0-{\Phi }_k.$$

So if $\Phi$ never falls below its starting value ${\Phi }_0$, the total actual cost is at most the total amortized cost. The usual way to arrange that is $\Phi \ge 0$ with a small ${\Phi }_0$. This is the step not to skip. A $\Phi$ that can end below where it started proves nothing, however neat the per-operation algebra looks.

Doubling. Take $\Phi =2·\text{size}-\text{cap}$. An append that does not resize has actual cost 1 and raises $\Phi$ by 2, so its amortized cost is 3. An append to a full array of capacity $\text{cap}$ has actual cost $1+\text{cap}$, while $\Phi$ changes by $2-\text{cap}$: size goes up by one, and the capacity doubles. The amortized cost is 3 again. Doubling keeps the array at least half full after the first append, so $\Phi$ stays at or above its start.

A binary counter. A counter of bits starts at 0 and is incremented $k$ times. An increment flips the trailing 1s to 0 and the next 0 to 1, and each flip costs 1. The worst increment flips every bit. Take $\Phi$ = the number of 1 bits. An increment that clears $t$ trailing ones costs $t+1$ and changes $\Phi$ by $1-t$, so it costs 2 amortized, whatever $t$ is. From 0, ${\Phi }_0=0$ and ${\Phi }_k$ is the number of ones in $k$, so the total is exactly $2k-(\text{ones in }k)<2k$.

def flips(k):
    """Bits flipped by each of k increments from 0.
    x ^ (x + 1) has a 1 exactly where the increment flips a bit."""
    return [bin(x ^ (x + 1)).count("1") for x in range(k)]

f16 = flips(16)
ones = [bin(x).count("1") for x in range(17)]   # Φ after x increments
assert f16 == [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5]
assert sum(f16) == 31
assert [i + 1 for i, f in enumerate(f16) if f >= 3] == [4, 8, 12, 16]   # highlighted
assert all(f + ones[i + 1] - ones[i] == 2 for i, f in enumerate(f16))
assert all(sum(flips(k)) == 2 * k - bin(k).count("1")
           for k in range(1, 2000))

Popping, and a rule that thrashes

A real list also shrinks, or a list that once held a million elements keeps a million slots for ever. Add pop, which removes the last element for a cost of 1. The mirror image of doubling seems natural: halve the capacity when the array becomes half full.

It fails on a sequence that sits on the boundary. Fill an array to size 8 in capacity 8, then alternate append and pop:

• the append finds the array full, so it doubles to 16 and copies 8: cost 9;
• the pop leaves 8 elements in 16 slots, which is half full, so it halves to 8 and copies 8: cost 9;
• the next append finds the array full again, and so on.

Every operation costs 9. At size $2^j$ every operation costs about $2^j$, so this sequence costs $\Theta (n)$ per operation for as long as it runs. The array thrashes. No accounting can rescue the rule, because the total really is quadratic.

def step(size, cap, op, shrink_at=4):
    """One append ('a') or pop ('p'), tracking only size and capacity.
    A stand-in for the real array: it returns the cost and stores
    nothing. Grow when full; shrink when a pop leaves
    shrink_at * size <= cap; never below capacity 2."""
    if op == "a":
        cost = 1
        if size == cap:
            cost += size
            cap *= 2
        return size + 1, cap, cost
    size, cost = size - 1, 1
    if cap > 2 and shrink_at * size <= cap:
        cost += size
        cap //= 2
    return size, cap, cost

def costs(ops, shrink_at=4):
    size, cap, out = 0, 2, []
    for op in ops:
        size, cap, cost = step(size, cap, op, shrink_at)
        out.append(cost)
    return out

wiggle = "a" * 8 + "apapap"
# halve at one half: thrash.  Halve at one quarter: calm.
assert costs(wiggle, shrink_at=2)[8:] == [9, 9, 9, 9, 9, 9]
assert costs(wiggle, shrink_at=4)[8:] == [9, 1, 1, 1, 1, 1]

The fix is to leave a gap. Double when an append finds the array full. Halve when a pop leaves it a quarter full (size $\le$ cap/4), never going below capacity 2. After a resize in either direction the array is exactly half full. From there it takes at least cap/2 appends to fill it, or about cap/4 pops to empty it to a quarter, before the next resize.

One potential for both directions

The doubling potential $2·\text{size}-\text{cap}$ goes negative as soon as the array is less than half full, so it cannot pay for shrinking. The potential that works measures the distance from half full, scaled so that it reaches the copy bill at both thresholds:

$$\Phi =\{\begin{array}{cc}2\text{size}-\text{cap}\hfill & \text{if }2\text{size}\ge \text{cap},\hfill \\ \text{cap}/2-\text{size}\hfill & \text{otherwise.}\hfill \end{array}$$

Here it is on nine appends followed by seven pops, from an empty array of capacity 2:

Checking the invariant means checking every kind of operation. Write $s$ for the size before the operation:

The growing append is the doubling argument again. For the shrinking pop, the size before the pop is $\text{cap}/4+1$, so $\Phi =\text{cap}/2-\text{cap}/4-1=\text{cap}/4-1$. After it, $\text{cap}/4$ elements sit in $\text{cap}/2$ slots, exactly half full, and $\Phi =0$. Every amortized cost is at most 3, and $\Phi \ge 0$ everywhere with ${\Phi }_0=1$ for the empty array of capacity 2.

Theorem. With grow-when-full and halve-at-one-quarter, every sequence of $k$ appends and pops from the empty array costs at most $3k+1$.

def phi(size, cap):
    return 2 * size - cap if 2 * size >= cap else cap // 2 - size

def trace(ops):
    """Rows (op, size, cap, cost, Φ after, amortized cost)."""
    size, cap, rows = 0, 2, []
    for op in ops:
        before = phi(size, cap)
        size, cap, cost = step(size, cap, op)
        after = phi(size, cap)
        rows.append((op, size, cap, cost, after, cost + after - before))
    return rows

rows = trace("a" * 9 + "p" * 7)
cost = [r[3] for r in rows]
pot = [r[4] for r in rows]
assert cost == [1, 1, 3, 1, 5, 1, 1, 1, 9, 1, 1, 1, 1, 5, 1, 3]
assert pot == [0, 2, 2, 4, 2, 4, 6, 8, 2, 0, 1, 2, 3, 0, 1, 0]
assert all(r[4] >= 0 and r[5] <= 3 for r in rows)
assert sum(r[3] for r in rows) == 36 <= 3 * 16 + 1
assert 2 * 3 - 8 == -2 and phi(3, 8) == 1   # one pop past the shrink

The implementation

The real array owns a block of cap slots and a count size. One helper, resize(new_cap), allocates a new block and copies the size elements across. It is the only line that costs more than 1. append resizes to twice the capacity if the array is full, then writes. pop removes the last element, then checks whether the array is now a quarter full and, if the capacity is above 2, resizes to half. Two details matter. The shrink test runs after the removal, and the minimum capacity stops a tiny array from shrinking to nothing. The lab has you build it and check the potential after every operation.

Complexity

• Model: one unit per element written, removed or copied; allocating a block is $O(1)$.
• Doubling, appends only: $n$ appends cost less than $3n$. Growth by a constant $c$: about $n^2/(2c)$, so $\Theta (n^2)$.
• Grow when full, halve at one quarter: every sequence of $k$ operations, starting from the empty array, costs at most $3k+1$, which is amortized $O(1)$ per operation. A single operation can still cost $\Theta (n)$. Space: once the array holds anything, it has fewer than $4·\text{size}$ slots.
• Halve at one half: $\Theta (n)$ per operation on a boundary sequence.
• Optimality: every append writes its element, so $\Omega (1)$ per operation is unavoidable. The constant 3 is not the point. The point is that $n$ has disappeared from the cost per operation.

When one slow operation is unacceptable, as in an audio callback, the cost can be de-amortized, at least for appends. When the array becomes half full, allocate the double-size block early, and let every later append also move two old elements across. By the time the old block is full, the new one already holds everything. Each append then costs $O(1)$ in the worst case, at the price of keeping two blocks alive. This is sketched, not proved, here.

Measure the claim

Cost per append, over $n$ appends, for three growth rules. Rule "CPython" is described in the next section:

Doubling sits just above 2, under its bound of 3. Growth by 4 grows linearly with $n$, as the arithmetic series says it must. The middle column stays below 10 without growing, because its capacities also form a geometric series, only with ratio about $9/8$ instead of 2. All the earlier copies put together are then about 8 times the latest one, rather than equal to it, so the copies total about 9 times the last copy, which is less than $9n$. These are measurements on appends only, in a model where every growth copies. The theorem covers every sequence.

def cpython_grow(cap):
    """New allocation when an append finds a CPython list full."""
    new_size = cap + 1
    return (new_size + (new_size >> 3) + 6) & ~3

def per_append(n, rule, start):
    return round(sum(append_costs(n, rule, start)) / n, 3)

rules = ((double, 1), (cpython_grow, 0), (plus4, 1))
table = {n: [per_append(n, *r) for r in rules]
         for n in (1000, 4000, 16000)}
assert table == {1000: [2.023, 8.556, 125.75],
                 4000: [2.024, 8.829, 500.75],
                 16000: [2.024, 9.4, 2000.75]}
assert all(per_append(n, cpython_grow, 0) < 10 for n in range(1, 20001))

What CPython does

CPython's list is a dynamic array, and its growth rule is the function list_resize in Objects/listobject.c. When an append needs room for new_size elements, it allocates new_size + new_size // 8 + 6 slots, rounded down to a multiple of 4. From an empty list the allocations are 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, and so on. That is growth by about one eighth, a constant factor above 1, so append is amortized $O(1)$ with a larger constant than doubling. (CPython hands the resize to the memory allocator's realloc, which can sometimes extend a block without copying, so our copy count is an upper bound on its work.)

Shrinking leaves a gap too. list.pop calls the same function, and it reallocates only when the size falls below half of the allocation. It then allocates about $9/8$ of the new size, not half of the old allocation, so the next append finds spare room and nothing thrashes.

import struct, sys

caps = [0]
while len(caps) < 10:
    caps.append(cpython_grow(caps[-1]))
assert caps == [0, 4, 8, 16, 24, 32, 40, 52, 64, 76]

if sys.implementation.name == "cpython" and sys.version_info >= (3, 12):
    ptr = struct.calcsize("P")
    slots = lambda lst: (sys.getsizeof(lst) - sys.getsizeof([])) // ptr
    lst, seen = [], [0]
    for i in range(80):
        lst.append(i)
        if slots(lst) != seen[-1]:
            seen.append(slots(lst))
    assert seen[:10] == caps          # the interpreter agrees
    lst = list(range(1000))
    while slots(lst) == 1000:
        lst.pop()
    # shrinks below half full, to about 9/8 of the size
    assert len(lst) == 499 and slots(lst) == 564
    for _ in range(100):              # wiggle there: no reallocation
        lst.append(0)
        lst.pop()
        assert slots(lst) == 564

A problem that looks different

A write-ahead log appends records to a file. Records die when they are superseded, but the file keeps their bytes. Whenever dead records outnumber live ones, a compaction pass rewrites every live record into a fresh file. One write can therefore trigger a rewrite of millions of records. What does a write cost over any sequence of writes and supersessions, and what would you charge each write so that compaction is always paid for? Nothing here mentions an array. The lab's last problem is a different one.

Practise

In the lab you prepay appends with credits and watch every cell's balance frame by frame, predict and then trace a binary counter that does not start at zero, build the growing and shrinking array with the potential checked after every operation, construct the sequence that makes the half-full rule thrash and measure it, and finish with a problem that doesn't say what it is.

Recap

• You can now: define amortized cost as a bound on every sequence and tell it apart from expected and worst-case cost; prove the doubling bound by the aggregate, banker's and potential methods; design a potential that pays for resizing in both directions; and explain why halving at one half thrashes.
• Invariant: $\Phi \ge 0$, every resize leaves the array half full where $\Phi =0$, and $\Phi$ has grown to pay the copies by the time the next resize comes.
• Complexity achieved: at most $3k+1$ units for any $k$ appends and pops from the empty array (amortized $O(1)$), against $\Theta (n)$ amortized per append for growth by a constant, and $\Theta (n)$ per operation on a boundary sequence for halving at one half.
• Failure mode: shrinking at the same threshold as growing, so that one boundary sequence resizes on every operation; or a potential that can fall below its start.
• In real software: CPython's list_resize grows a list by about one eighth plus a small constant, and shrinks only below half full, to about $9/8$ of the size.
• Retrieval: the chained dictionary from Universal and Perfect Hashing doubles its table and redraws the hash function whenever $n>m$, rehashing every key. What does one insert cost in the worst case, and what does an insert cost over any sequence?

Check yourself

1. Why does the grow-and-shrink array have amortized cost at most 3, and why does its potential need two pieces?
2. Grow by 50% ($\text{cap}\leftarrow \lceil 1.5·\text{cap}\rceil$) instead of doubling. Is append still amortized $O(1)$? Give a potential, or a counterexample.
3. Compare amortized $O(1)$ appends with the de-amortized array that is $O(1)$ in the worst case. When would you pay for the second, and what does it cost?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.