Symptom

You have a dynamic array. push writes one element and bumps a counter, which is clearly $O(1)$ — except when the array is full, in which case it allocates a new buffer of twice the size, copies every element across, and frees the old one. That is $O(n)$.

So what do you tell the person reviewing your design doc? The worst-case cost of push is $O(n)$, and that is a true statement. It is also close to useless: it suggests that $n$ pushes cost $O(n^2)$, which is off by a factor of $n$ from what actually happens. Everyone knows the resize is “rare enough not to matter,” and everyone says so with a hand-wave.

The hand-wave is the problem. “Rare enough” is not an argument, and the cases where the intuition is wrong look identical to the cases where it is right. If you grow the array by a constant rather than doubling it, resizes are still rare — every 1024 pushes, say — and the total is still $\Theta(n^2)$. Rarity alone does not save you. Something else does, and you need to be able to say what.

There is a second, worse symptom: you reach for the wrong tool. Reviewers who know the worst case is bad will ask for the average case, and someone will compute an average over a probability distribution on inputs that nobody has justified. Dynamic arrays have no randomness in them. The resize is not unlikely; it is entirely determined by the sequence of calls. Averaging is the wrong frame, and it will produce a number that means nothing.

Statement

For a sequence of operations, define a potential function $\Phi$ mapping each state of the data structure to a real number, with $\Phi(D_0) = 0$ and $\Phi(D_i) \ge 0$ for all $i$. Define the amortized cost of operation $i$ as

$$\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$$

where $c_i$ is the actual cost. Then for any sequence of $n$ operations,

$$\sum_{i=1}^{n} c_i = \sum_{i=1}^{n} \hat{c}_i - \Phi(D_n) + \Phi(D_0) \le \sum_{i=1}^{n} \hat{c}_i.$$

The total actual cost is bounded by the total amortized cost. If you can show each $\hat{c}_i \le k$, you have shown $n$ operations cost at most $kn$, regardless of which operations they were or what order they came in.

Note what this is not. It is not a probabilistic claim: there is no distribution, no expectation, no “typical” input. The bound holds for the adversary’s worst sequence. It is also not a claim about any individual operation, which may still cost $\Theta(n)$. It is a claim about totals, and totals are usually what you actually care about.

Argument

The proof of the theorem itself is one line: the sum telescopes. Every $\Phi(D_i)$ appears once positively and once negatively except the endpoints, so $\sum \hat{c}_i = \sum c_i + \Phi(D_n) - \Phi(D_0)$. Since $\Phi(D_0) = 0$ and $\Phi(D_n) \ge 0$, dropping the potential terms only weakens the bound in the safe direction. That is the entire theorem.

All the content is in choosing $\Phi$. The way to think about it: $\Phi$ is prepaid work. Cheap operations are charged a little extra, which accumulates in the potential; expensive operations spend it down. The two conditions — starts at zero, never goes negative — are exactly the statement that you cannot spend money you never earned.

The dynamic array. Let $n$ be the number of elements and $s$ the allocated size. Take $\Phi = 2n - s$. Just after a resize, $n = s/2$, so $\Phi = 0$. Each push increments $n$, raising $\Phi$ by 2, and costs 1, so $\hat{c} = 1 + 2 = 3$. When a push triggers a resize at $n = s$, the actual cost is $n + 1$ (copy $n$ elements, write one). Before: $\Phi = 2n - n = n$. After: $n’ = n+1$, $s’ = 2n$, so $\Phi’ = 2(n+1) - 2n = 2$. The amortized cost is $(n+1) + 2 - n = 3$. Constant, both cases. So $n$ pushes cost at most $3n$.

Now watch what happens with a constant growth increment $k$. Between resizes you get $k$ pushes to prepay a copy of size $n$, so each push would have to bank $n/k$ — which grows with $n$, so no constant $\Phi$ can work. The potential method does not just prove doubling works; it shows precisely why the alternative does not, and it locates the failure in the growth rule rather than in the frequency of resizes. Any geometric growth factor $\alpha > 1$ works, with amortized cost $1 + \alpha/(\alpha - 1)$: 3 for $\alpha = 2$, and 4 for $\alpha = 1.5$, which is what several real allocators use so that freed blocks can be reused for a later growth.

The binary counter. Incrementing an $n$-bit counter flips a variable number of bits: 0111 → 1000 flips four. Let $\Phi$ be the number of 1 bits. An increment that flips $t$ trailing ones to zero and one zero to one costs $t + 1$ and changes the potential by $1 - t$. Amortized: $(t+1) + (1-t) = 2$. So $n$ increments flip at most $2n$ bits, no matter the starting value. The proof does not care that the expensive increments are rare; it cares that each 1 bit was paid for when it was created.

Where it gets deep. The same machinery, with a cleverer $\Phi$, is what proves splay trees are $O(\log n)$ amortized without storing any balance information, and Fibonacci heaps’ $O(1)$ amortized decrease-key — which is what makes Dijkstra $O(E + V \log V)$. In both cases no individual operation is fast, and the structure is only efficient as a whole. That is not a weakness of the analysis; it is a design strategy the analysis makes available. You are permitted to build a data structure that is sometimes slow, provided you can name the potential.

Forbids

The theorem is a proof technique, so what it forbids is a class of wrong conclusions rather than a class of algorithms:

It forbids concluding $O(n^2)$ from a worst case of $O(n)$ per operation. Multiplying the worst case by the number of operations is valid but frequently loose by a factor of $n$. If the operations interact through shared state, worst cases may not be simultaneously achievable, and the potential function is how you prove they are not.

It forbids a “sometimes slow” structure hiding an actual $\Theta(n)$ average. The bound cuts both ways: if no valid $\Phi$ exists, no amortized bound exists, and the adversary really can make every operation expensive. Failure to find a potential is evidence, and the constant-growth array is the canonical case.

It forbids treating amortization as a probabilistic claim. There is nothing to be unlucky about. An adversary choosing the worst possible sequence gets the same bound.

Does not forbid

It does not promise any individual operation is fast, and this is the misuse that reaches production. A dynamic array push is amortized $O(1)$ and can still take 200 ms when it copies a gigabyte. If you have a latency SLO, amortized bounds are the wrong instrument — your p99.9 sees exactly the operations the amortization averaged away. This is why real-time systems use std::vector::reserve, why the Go runtime and the JVM both moved to incremental and concurrent collectors rather than faster stop-the-world ones, and why Redis’s incremental rehashing moves a few buckets per command instead of rebuilding the table at once. Each of those is the same trade: give up a better amortized bound to get a better worst case.

It does not require the data structure to be randomized or the input to be benign. Hash tables with random probing need probability. Dynamic arrays, binary counters, and union-find do not — union-find’s $O(\alpha(n))$ bound is amortized and fully deterministic.

It does not stop being valid under adversarial input. This is worth separating from the previous point because it is the most common confusion. People assume that anything with “average” flavor breaks against an attacker. Amortized bounds do not: an attacker who controls the entire call sequence still cannot exceed $3n$ pushes’ worth of work. Hash-flooding attacks work against expected-time hashing, not against amortized bounds.

It does not require operations to be uniform. Splay trees amortize a mixed workload of searches, insertions and deletions under a single potential, and the deep results in this area (Sleator and Tarjan’s access lemma) bound non-uniform access patterns better than uniform ones.

Boundary

  • Amortized vs. average vs. expected. Three different claims. Amortized is worst-case over sequences, with no probability. Average-case assumes an input distribution. Expected-time assumes internal randomness. Quicksort with a random pivot is expected $O(n\log n)$; a dynamic array is amortized $O(1)$; they are not the same kind of statement and mixing them up produces guarantees you do not have.
  • The accounting method. An equivalent formulation: assign each operation a charge, let cheap ones bank credit on specific objects, and require the balance to stay non-negative. It is often easier to invent than a potential function, and translating between them is mechanical.
  • Persistence breaks it. Amortized bounds assume the structure is used linearly. If a functional data structure lets you re-run the same expensive operation from an old version repeatedly, the prepaid work is spent many times. Okasaki’s lazy evaluation with memoization restores the bounds, which is the whole subject of Purely Functional Data Structures.
  • The same tool proves lower bounds. The weight function in an adversary argument (T005) is a potential function used in reverse: bound how much one comparison can change it, and the start and end values force a minimum operation count. Upper and lower bounds, one technique.
  • Amortization and the online setting. Bounding a sequence when you cannot see the future is the competitive-analysis question, and potential functions are the standard tool there too, which is why this post sits in Part X beside the performance results rather than in Part I.