Amortized Analysis, in depth: what the guarantee promises, choosing a method, deamortization and measured tail cost

What an amortized bound promises

Write the actual cost of operation i as t_i and its amortized cost as a_i. An amortized analysis proves that for every sequence of n operations starting from the initial state, the sum of t_i is at most the sum of a_i. If every a_i is O(1), then n operations cost O(n), so the average per operation over that sequence is O(1). Three things are absent from that statement, and each one has caught engineers out.

• No probability. The bound holds for every sequence, including one chosen by an adversary who knows your code. That separates it from an average-case bound, which assumes a distribution over inputs, and from an expected bound, which averages over the algorithm's own random choices. Hash tables with random hash functions give expected O(1) lookups; resizing them gives amortized O(1) inserts. Those are different claims combined.
• No per-operation ceiling. One operation can cost Θ(n). Amortized O(1) only says the expensive ones are rare enough to be paid for by the cheap ones around them.
• No guarantee for a suffix. The bound covers sequences from the initial state. If you snapshot a structure just before an expensive operation and replay that operation many times, as persistent or backtracking code does, the prepaid budget is spent repeatedly and the bound is void.

In short: an amortized bound is a guarantee on throughput, not on latency. If your concern is how long a batch job takes, it is exactly the right tool. If your concern is the 99.9th percentile of a request path, it tells you nothing until you deamortize.

Three ways to prove one

There are three standard ways to prove an amortized bound. They prove the same kind of statement and differ only in bookkeeping, so the choice is about which argument is easiest to write down and check.

A practical order: try aggregate first, because it is a single inequality. If different operations need different costs, switch to accounting. If the credits are smeared across the structure, as with rotations in a tree, write a potential. The potential method is the most general; in the potential formulation a_i = t_i + Φ_i − Φ_i−1, the terms telescope, and the sum of actual costs is the sum of amortized costs minus (Φ_n − Φ₀). That difference is non-negative by the requirement above, so the actual total never exceeds the amortized total.

Where amortized bounds live

Amortized bounds appear in most of the structures you use every day. Knowing which bounds are amortized tells you where latency spikes can come from.

The worked analyses live elsewhere: union-find for the α(n) bound, splay trees for the access lemma, and hash tables for load factors and resizing policy.

Worked example: a million appends

Take one million appends to a doubling array that starts with capacity 1. Count a unit of work for each element write and each element moved during growth. Growth happens when the array is full at sizes 1, 2, 4, and so on up to 524,288, and the moves sum to 1 + 2 + ... + 524,288 = 1,048,575. Add one million writes and the total is 2,048,575, an average of 2.05 units per append. That is the aggregate argument in one line.

Now look at the single most expensive append. It is the one that finds 524,288 elements in a full array and copies all of them: 524,289 units for one call. The average is 2.05; the maximum is about 250,000 times larger. The figure shows the first 64 appends. In the top row the spikes double each time. In the bottom row the same work is spread out, which is the subject of the next section.

Deamortization: doing the work before it is due

Deamortization removes the spikes by starting the expensive work before it is due and doing a constant slice of it inside each cheap operation. For a dynamic array the trick is to keep two buffers during growth. When the old buffer of capacity C fills, allocate a buffer of capacity 2C, write new elements straight into it, and copy a fixed number of old elements per append. Reads below C go to the old buffer, which stays valid until the switch; reads at or above C go to the new one.

class IncrementalArray:
    """Deamortized doubling: migrate a constant number of old slots per append."""
    MOVES_PER_OP = 2

    def __init__(self):
        self.cap, self.n = 1, 0
        self.buf = [None]
        self.new = None          # larger buffer being filled in the background
        self.moved = 0           # prefix of buf already copied into new

    def append(self, x):
        work = 1
        if self.new is None and self.n == self.cap:
            self.new = [None] * (2 * self.cap)
            self.moved = 0
        if self.new is not None:
            self.new[self.n] = x                      # new writes go straight to the new buffer
            k = min(self.MOVES_PER_OP, self.cap - self.moved)
            for i in range(self.moved, self.moved + k):
                self.new[i] = self.buf[i]
            self.moved += k
            work += k
            if self.moved == self.cap:                # migration finished: switch over
                self.buf, self.cap, self.new = self.new, 2 * self.cap, None
        else:
            self.buf[self.n] = x
        self.n += 1
        return work

    def get(self, i):
        if self.new is not None and i >= self.cap:
            return self.new[i]          # written after the migration started
        return self.buf[i]              # old buffer stays valid until the switch

The correctness argument is a race that the copier must win. Migration starts when the array holds C elements and the new buffer has room for 2C. Copying two old elements per append finishes the C old elements after C/2 appends, when the array holds 1.5C elements, well before the new buffer fills. Copying one per append would finish exactly when the new buffer filled, which works but leaves no slack; two gives a margin and simplifies the edge cases. The general rule is to pick a migration rate that completes the move before the next trigger can fire, with the inequality written in a comment next to the constant.

Measured: same total, different worst case

Running both classes for one million appends and recording the work returned by each call gives the following, and an assertion confirms that every index reads back its value.

The totals are identical because every element is still copied once per growth. Only the distribution changed. One caveat is easy to miss: this counter measures element moves, not allocation. Allocating and zero-filling a buffer of 2C slots is itself O(C) in most runtimes unless the allocator hands back lazily zeroed pages, so a fully deamortized array also needs an allocator whose cost does not grow with the request, or pre-allocated capacity. Garbage collection of the old buffer is another deferred cost you did not see in this table.

Deamortization in production systems

The same pattern shows up wherever a system cannot afford a pause.

• Redis dictionaries. Redis keeps two hash tables during a resize and moves buckets from the old one to the new one a step at a time: each dictionary operation performs a small rehash step, and with active rehashing enabled the server also spends a bounded slice of its periodic cron on it. Lookups consult both tables until the move completes; new keys go to the new table. That is the incremental array above, applied to buckets.
• Real-time functional queues. The two-stack queue reverses its inbox in one burst. Hood and Melville, and later Okasaki, showed how to perform that reversal a few steps per operation so that every operation is O(1) in the worst case, which also makes the queue safe to use persistently.
• Global rebuilding. For structures that degrade slowly, such as a balanced tree with lazy deletions, build a fresh copy in the background a constant number of steps per update, replay the updates that arrived during the build, then swap.
• Incremental and concurrent garbage collectors. They trade a stop-the-world pause for many short slices of marking work interleaved with the program, the same move at the scale of the whole heap.

Failure modes

These are the ways amortized structures hurt systems in practice.

• Spikes on the request path. A cache map that doubles from 8 million to 16 million entries rehashes everything inside one unlucky request. Look for p99.9 outliers that line up with powers of two in the size metric.
• Repeated replay of an expensive step. Undo stacks, snapshots, speculative execution and backtracking search can return to the state just before a resize and pay for it again and again. See the persistence discussion in the accounting method article.
• Thrashing thresholds. Growing when full and shrinking when half full lets an alternating push and pop at the boundary trigger a full copy every operation, so the amortized bound silently becomes Θ(n). Shrink at one quarter instead, so there is a gap of Θ(n) cheap operations between resizes.
• Mixing operations the proof did not cover. A binary counter is amortized O(1) per increment. Allow decrements and the sequence that alternates around 0111...1 flips every bit each time.
• Shared structures. When many tenants share one amortized structure, whoever triggers the expensive step pays for everyone, which is an unfairness problem even when the aggregate throughput is fine.

Trade-offs

Deamortization is not free. Both variants briefly hold the old C slots and the new 2C slots, but classic doubling releases the old buffer within one call, while the incremental array keeps both for C/2 appends, and every read needs a branch to choose a buffer. Throughput is usually a little worse, because the copy loop runs in small pieces with poorer locality than one bulk copy that a library can vectorise. The code is harder to get right: the race between copier and producer is a real invariant that needs a test. Choose amortized structures for batch work and throughput-bound services, and deamortized ones for interactive paths, real-time systems, and anything with a strict tail-latency objective. A third option is often the cheapest: size the structure up front from a known bound and avoid growth on the hot path entirely.

What to do next

1. List the amortized structures on your latency-critical paths: dynamic arrays, hash maps, queues built from stacks, and anything that compacts or rebuilds.
2. For each, find the expensive step and ask whether one request can trigger it. If so, either pre-size, deamortize, or move the work off the request thread.
3. Instrument the expensive step itself, such as resize count and duration, rather than inferring it from overall latency.
4. When you write an amortized proof, state the starting state and the allowed operations, and check that snapshots or undo do not replay expensive steps.
5. When you deamortize, write the migration-rate inequality next to the constant and add a test that interleaves reads with growth, as the assertion above does.
6. Work through the three method pages in order: aggregate, accounting, potential.