Amortized Analysis

Amortized analysis bounds the average cost per operation across a sequence, even when a single operation can be expensive. The classic example: a dynamic array’s append is O(n) in the worst case (the resize step copies everything), but O(1) amortized — because the expensive resizes are rare and their cost can be “spread out” over the cheap appends that came before. There are three standard methods — aggregate, accounting, potential — that all give the same answer but differ in how the bookkeeping is done.

1. Intuition — Saving for the Rainy Day

A useful analogy. Imagine a streaming service that bills you a flat $10/month for unlimited movies. In any given month, your actual viewing cost varies — some months you binge for hours (the service spends a lot to stream them), other months you don’t watch at all (the service spends nothing). From your perspective the per-month average is $10. From the service’s perspective they have engineered the pricing so that the heavy-use months are subsidised by the light-use months. No single month is metered exactly; the average over many months is the meaningful number.

That is exactly what amortized analysis does for algorithms: it gives a price tag per operation, averaged over a sequence, that is robust against occasional expensive operations. If you can show that any sequence of n operations takes at most T_total total time, then the amortized cost per operation is T_total / n — even if some individual operations were much more expensive than that.

The catch: amortized analysis is only correct over a sequence, not for a single operation. The first call to append in a dynamic array might cause a O(n) resize. But across a long-enough sequence, the average smooths out. Amortized bounds do apply to worst-case sequences (the analysis is a worst-case argument, just over a sequence rather than a single op) — they just don’t apply to single operations in isolation.

Amortized is deterministic, not probabilistic. This is the single most-confused point about the technique. Amortized analysis examines “a sequence of operations” and computes a worst-case bound on the total cost of any such sequence; it makes no distributional assumption about the inputs (Wikipedia, Amortized analysis; see also Tarjan 1985). Average-case analysis, by contrast, is a probabilistic statement: “averaged over inputs drawn from some distribution, the cost is X.” When this note (and the broader literature following Tarjan) says “amortized cost,” it means worst-case amortized cost over the worst possible sequence of operations starting from a fixed initial state — a deterministic bound. The word “average” in “average per operation” refers only to dividing total cost by number of operations, not to averaging over randomness. The distinction matters: an amortized bound holds adversarially, an average-case bound only holds in expectation. See §10.4 for the canonical confusion (quicksort’s O(n log n) is average-case, not amortized).

2. Tiny Worked Example — Push to a Dynamic Array

A dynamic array (Python list, C++ std::vector, Java ArrayList) is a fixed-capacity buffer that doubles when full. Pushing n items one at a time:

Push #	Action	Cost
1	write to slot 0; capacity 1	1
2	full; resize (copy 1 elem); write	1 + 1 = 2
3	write	1
4	full; resize (copy 2); write	2 + 1 = 3
5–7	write × 3	3
8	full; resize (copy 4); write	4 + 1 = 5
…	…	…

Total cost across n pushes: each insert costs 1 (n total), and resizes cost 1 + 2 + 4 + 8 + ... + n/2 < 2n (geometric series). So T_total = n + 2n = 3n = O(n). Per-operation amortized cost: 3n / n = 3 = O(1). Amortized O(1) push, even though the worst single push is O(n).

This is the canonical example. The geometric resize ratio (doubling) is what makes it work — if instead you grew the array by adding a fixed number of slots each time (linear growth), the total cost would be Θ(n²) and the amortized cost Θ(n) per push. The doubling matters; the size of the constant doesn’t.

3. Three Methods, One Answer

There are three canonical methods to do amortized analysis (CLRS Ch. 17). All three give the same answer for the same problem; they differ in how the proof is presented. The choice of method is a matter of which is easiest to argue for a specific data structure.

Method	What you compute	Mental model
Aggregate	Total cost across n ops, then divide	”Sum it all up; average over n”
Accounting (banker’s)	Per-op charge with credit accounts	”Overcharge cheap ops; spend the savings on expensive ops”
Potential (physicist’s)	A function Φ(state) of the data structure; amortized = actual + ΔΦ	”Stored energy in the configuration”

Tarjan’s seminal 1985 paper Amortized Computational Complexity (SIAM J. Algebraic Discrete Methods 6(2), pp. 306–318) introduced and unified the latter two. The aggregate method is older and used informally before that.

4. Method 1 — Aggregate

The simplest. Compute the total cost of any sequence of n operations, then divide by n.

4.1 Recipe

T_total(n) := the total cost of a worst-case sequence of n operations
T_amortized := T_total(n) / n

If T_total(n) = O(f(n)) then each operation has amortized cost O(f(n) / n). No per-op bookkeeping; you just sum.

4.2 Worked Example — Dynamic Array Doubling

Per §2, total cost over n pushes is ≤ 3n. So:

T_amortized = 3n / n = O(1)

Aggregate is the easiest method when the total cost is easy to write as a closed-form sum. It becomes awkward when different types of operation interleave (e.g., mix of pushes and pops, or insertions and deletions) — that’s when the accounting and potential methods earn their keep.

4.3 Worked Example — Stack with MULTIPOP

Consider a stack supporting PUSH, POP, and MULTIPOP(k) (pop up to k elements). Worst-case MULTIPOP is O(k) which can be O(n) if the stack is full.

But: across any sequence of n operations starting from an empty stack, at most n items have ever been pushed. Every item that’s ever popped (by POP or MULTIPOP) must first have been pushed. So the total pop work across the sequence is at most the total push work, which is O(n). Total cost across all operations: O(n). Amortized cost per op: O(1).

This is the cleanest example of aggregate analysis: you can’t bound a single MULTIPOP by O(1), but you can bound the sum of all the MULTIPOP costs because each pop is paid for by an earlier push.

5. Method 2 — Accounting (Banker’s Method)

Here we assign each operation a fixed amortized cost, possibly higher than its actual cost. The difference (overcharge) is deposited as credit on the data structure. Expensive operations later withdraw from this credit pool to pay their actual cost.

5.1 Recipe

Choose amortized costs ĉ_i for each op type such that:
  for any prefix of operations,  Σ ĉ_i  ≥  Σ c_i  (actual cost)

The total credit on the structure is always ≥ 0 (you can never go in debt).
The amortized bound: T_total ≤ Σ ĉ_i.

The key invariant is non-negative credit balance at all times. If you can satisfy this with chosen ĉ_i, then the amortized costs upper-bound the actual total cost.

5.2 Worked Example — Dynamic Array Doubling, Accounting Style

Charge each push an amortized cost of ĉ = 3:

• 1 unit pays for the immediate insert.
• 1 unit is credit deposited on the just-inserted item.
• 1 unit is credit deposited on an existing item that has not yet been copied in any resize.

When a resize happens at capacity k, the array doubles to 2k. The resize copies k items. Each of those k items has 1 credit on it (deposited when it was inserted, since the previous resize). So the resize is paid for entirely by the credits already accumulated. The credit account is invariantly non-negative, so amortized cost ĉ = 3 = O(1) is a valid bound.

5.3 Worked Example — Stack with MULTIPOP, Accounting Style

Charge PUSH an amortized cost of 2: 1 for the push, 1 deposited as credit on the just-pushed item. POP and each unit of MULTIPOP charge 0 amortized — they pay using the credit on the popped item. Credit is always ≥ 0 (every item on the stack has 1 credit). So amortized: O(1) per push, O(0) per pop = O(1) per operation.

5.4 Why “Banker’s”

Tarjan called this the banker’s method because the data structure’s “state” is treated like a bank account: deposits and withdrawals must net non-negative. The bookkeeping mirrors a bank ledger. The metaphor is concrete enough to be intuitive but precise enough to be rigorous.

6. Method 3 — Potential Function (Physicist’s Method)

The most general and most flexible. Define a function Φ : DataStructureState → ℝ (a “potential”) that maps each possible state of the data structure to a real number, and then define the amortized cost as actual cost plus the change in potential.

6.1 Definition

Let D_i denote the state of the data structure after the i-th operation. Let c_i be the actual cost of the i-th operation, and let Φ(D_i) be the potential after the i-th operation. Define:

ĉ_i  :=  c_i  +  Φ(D_i) − Φ(D_{i−1})
       =  c_i  +  ΔΦ_i

where:

• c_i is the actual cost of operation i.
• Φ(D_i) − Φ(D_{i−1}) is the change in potential caused by operation i. If the operation made the structure “harder,” potential goes up and ĉ_i > c_i (we are charging the operation for setting up future expense). If the operation made the structure “easier,” potential goes down and ĉ_i < c_i (the operation is paid for by the potential it released).
• ĉ_i is the amortized cost of operation i.

Summing over n ops:

Σ ĉ_i  =  Σ c_i  +  Φ(D_n) − Φ(D_0)

So the total amortized cost differs from the total actual cost by the net change in potential. If Φ(D_n) ≥ Φ(D_0) (the final state has potential at least as much as the initial state), then Σ ĉ_i ≥ Σ c_i and amortized costs upper-bound actual total cost.

In practice we choose Φ such that Φ(D_0) = 0 (empty structure, zero potential) and Φ(D_i) ≥ 0 (non-negative for all reachable states). Under these two conditions, Σ ĉ_i ≥ Σ c_i for all n, so the amortized bound is valid.

6.2 Choosing a Good Potential

The art of the potential method is picking a Φ such that:

1. Φ(D_0) = 0 and Φ(D_i) ≥ 0 always.
2. Cheap operations have small ΔΦ (so amortized cost stays small).
3. Expensive operations consume potential (ΔΦ very negative), pushing their amortized cost down.

A good potential function is one that captures the “looming expense” embedded in the current state. For dynamic-array doubling, a natural potential is Φ = 2 · num_items − capacity. When the array is half-full, Φ = 2·(k/2) − k = 0. When the array is full, Φ = 2·k − k = k. The next push triggers a resize costing k, and immediately after, Φ = 2·(k+1) − 2k = 2. So ΔΦ = 2 − k, and the amortized cost of that push is c_i + ΔΦ = (k + 1) + (2 − k) = 3 = O(1). ✓ All other pushes (no resize) cost c_i = 1 and increase Φ by 2, giving amortized cost 3. Same answer as the aggregate and accounting methods.

6.3 Why “Physicist’s”

The metaphor is stored energy: the data structure is in a state that has a certain potential energy; operations either increase the energy (you’re paying to charge the system) or decrease it (you’re harvesting work from the stored energy). Tarjan introduced this name because the bookkeeping resembles the way physicists track conservative forces and work-energy theorems.

The potential method is more general than the accounting method — it is in fact the limit of the accounting method as you let the credits be real numbers attached to the whole state rather than discrete units attached to individual items. Any accounting argument can be re-cast as a potential argument; the converse is harder.

7. Canonical Examples — Where Amortization Earns Its Keep

7.1 Dynamic Array (Already Done Three Ways)

O(1) amortized push, O(n) worst-case single push. The geometric resize ratio is essential — linear growth would give Θ(n) amortized.

7.2 Union-Find with Path Compression and Union by Rank

The Union-Find data structure with both path compression (flattening trees during find) and union by rank (always attaching the shallower tree under the deeper) achieves amortized cost O(α(n)) per operation, where α(n) is the inverse Ackermann function — a function that grows so slowly that for any practical n (say, n < 2^65536), α(n) ≤ 4. So in practice, Union-Find is amortized O(1), but the theoretically tight bound is O(α(n)).

This was proved by Tarjan in 1975 (Efficiency of a Good But Not Linear Set Union Algorithm, JACM 22(2)) using a sophisticated potential function. The proof is one of the deepest amortized-analysis arguments in the algorithm literature. Without amortization, the per-operation worst case for Union-Find is O(log n) — the amortized analysis is what gives the famous near-constant guarantee.

7.3 Splay Tree

A self-adjusting binary search tree (Sleator & Tarjan 1985, JACM 32(3)) whose every operation has amortized cost O(log n) even though individual operations can take O(n) in the worst case. The key idea: every access “splays” the accessed node to the root via a sequence of rotations; the splay step both performs the access and rebalances the tree for future accesses. The potential function used in the proof is Φ = Σ_{x in tree} log(size(x)) — the sum over nodes of the log of the subtree size at each. The proof shows that the rotations during splay decrease this potential by enough to amortize their cost down to O(log n). See Sleator & Tarjan 1985 §3 for the full argument.

7.4 Fibonacci Heap Decrease-Key

Fibonacci heaps (Fredman & Tarjan 1987, JACM 34(3)) support decrease-key in amortized O(1) time. The amortized analysis uses a potential function Φ = #trees + 2 · #marked nodes and is what makes Dijkstra’s algorithm achieve O(E + V log V) (rather than O(E log V) with a binary heap) when implemented with Fibonacci heaps. See Dijkstra’s Algorithm.

7.5 Stack with MULTIPOP (CLRS Ch. 17.1)

Already covered — O(1) amortized despite O(n) worst-case MULTIPOP.

7.6 Binary Counter Increment

Incrementing an n-bit binary counter from 0 takes Θ(n) worst-case time for a single increment (when going from 01...1 to 10...0, all bits flip). But amortized, each increment is O(1) — over n increments from 0, the total number of bit flips is < 2n (bit i flips every 2^i increments, so total flips = Σ n/2^i ≤ 2n). Aggregate analysis: amortized O(1) per increment.

8. Pseudocode — How to Set Up an Amortized Argument

Method 1 (Aggregate):
  bound the total cost T(n) of n operations
  return T(n) / n  as the amortized cost per op

Method 2 (Accounting):
  pick amortized cost ĉ_i for each op type
  show that a credit invariant (≥ 0) is preserved after each op
  return max(ĉ_i)  as the amortized cost per op

Method 3 (Potential):
  pick Φ : state → ℝ with Φ(D_0) = 0 and Φ(D_i) ≥ 0 for all i
  for each op type, compute ĉ_i = c_i + ΔΦ_i and verify it is small
  return max(ĉ_i)  as the amortized cost per op

9. Python Implementation — Dynamic Array with Doubling

A from-scratch dynamic array, with comments labelling the cost model:

class DynamicArray:
    def __init__(self):
        self._cap = 1                    # initial capacity
        self._n = 0                      # number of elements
        self._buf = [None] * self._cap
 
    def append(self, x):
        if self._n == self._cap:         # rare: O(n) resize
            self._cap *= 2
            new_buf = [None] * self._cap
            for i in range(self._n):
                new_buf[i] = self._buf[i]
            self._buf = new_buf
        self._buf[self._n] = x           # always: O(1) write
        self._n += 1
 
    def __getitem__(self, i):
        if i < 0 or i >= self._n:
            raise IndexError
        return self._buf[i]              # O(1) read
 
    def __len__(self):
        return self._n

The append method has two regimes: the common case where self._n < self._cap (a single write, O(1)) and the rare case where the buffer is full (allocate, copy, write — O(n)). The geometric doubling ensures the rare case happens exponentially less often as n grows. Total work across n appends: O(n). Amortized per append: O(1).

Note that Python’s built-in list uses over-allocation with a slightly different growth pattern (it grows the capacity by factors of about 1.125 plus a small constant — see CPython Objects/listobject.c), but the analysis is unchanged: any constant-factor geometric growth gives amortized O(1) push.

10. Variants, Subtleties, and Edge Cases

10.1 Why Doubling and Not Tripling?

A growth factor of r gives amortized cost r / (r − 1) per push (the geometric series sum). For r = 2 this is 2; for r = 1.5 it’s 3; for r = 4 it’s 4/3 ≈ 1.33. So any r > 1 gives amortized O(1) — but lower r wastes less memory at the cost of more frequent resizes, while higher r resizes less often but wastes more memory. Most implementations pick r ≈ 1.5 to 2 as a compromise.

A growth factor of r = 1 (i.e., adding a constant Δ each time) makes the total cost Θ(n²) and the amortized cost Θ(n) — disastrous.

10.2 What About Pop and Shrink?

If the array also supports pop, you might want it to shrink when much of the buffer is empty. Naive shrinking when half-full can cause an O(n) re-amortization disaster: imagine a workload that alternates push/pop at the boundary n = cap/2, each one triggering a resize. The total cost becomes Θ(n²).

The standard fix: only shrink when the array is at most 1/4 full (not 1/2). Then a shrink halves the capacity, leaving the array 1/2 full again — far from either boundary. This buffer prevents the alternating-resize disaster, and amortized cost stays O(1).

10.3 Amortized vs Worst-Case Real-Time Bounds

Amortized bounds say nothing about individual operation latency. A single dynamic-array push can take O(n) time. For real-time systems where every operation must finish in bounded time (e.g., audio processing, robotics, embedded), amortized bounds are not enough — you need worst-case bounds.

There are data structures that achieve worst-case (not just amortized) O(1) push: deamortized dynamic arrays that gradually copy the old buffer into the new one as part of subsequent push operations. The theory is subtle (see Brodnik et al. 1999, Resizable Arrays in Optimal Time and Space) but the upshot is: amortized O(1) can be converted to worst-case O(1) with extra cleverness, at the cost of some auxiliary state.

10.4 Amortized Doesn’t Mean Average-Case

The biggest confusion: amortized analysis is not the same as average-case analysis.

• Average-case is a probabilistic statement: “averaged over random inputs, the cost is X.”
• Amortized worst-case is a deterministic statement: “even on the worst possible sequence of operations starting from an empty structure, the per-op average is X.”

Quicksort is O(n log n) average case (over random pivots / random inputs), but each comparison is just a comparison — no amortization is happening. Dynamic array push is O(1) amortized, deterministic over any sequence of pushes from empty. Different concepts; same word “average” muddles them.

11. Pitfalls

11.1 Reporting Amortized Bound Without Saying “Amortized”

Saying “dynamic array push is O(1)” is misleading — a careful interviewer will ask “single op?” and you should clarify “amortized over a sequence; single op can be O(n) during a resize.” Always say the word “amortized” when you mean it.

11.2 Confusing Amortized with Average-Case

Two different concepts (see §10.4). Amortized worst-case is deterministic over sequences; average-case is probabilistic over inputs. Don’t conflate.

11.3 Wrong Initial Potential

If you pick Φ(D_0) ≠ 0, your “amortized” cost is shifted by Φ(D_0). The bound is still valid but harder to interpret. Convention: Φ(D_0) = 0 and Φ(D_i) ≥ 0 for all reachable D_i.

11.4 Forgetting That Credit Cannot Go Negative

In the accounting method, if you ever have a state where the credit account is negative, your bound is invalid — you “borrowed” from the future. The invariant must hold at every step, not just at the end.

11.5 Treating Amortized as Real-Time

Don’t promise amortized O(1) for a real-time system without checking that the worst-case operation latency is acceptable. A O(n) resize can introduce a hiccup that ruins a real-time deadline even if the average is O(1).

11.6 Picking a Potential That Isn’t Bounded Below by 0

If your potential function can go negative on some reachable state, the inequality Σ ĉ_i ≥ Σ c_i might fail and your amortized bound is wrong. Always verify Φ(D_i) ≥ Φ(D_0) for every reachable state.

11.7 Over-Aggressive Shrinking

In dynamic-array implementations, shrinking when half-full creates a Θ(n²) worst-case sequence (alternating push/pop at the boundary). Shrink only when ≤ 1/4 full. Same fix applies to many other “doubling” structures with deletion.

12. Diagram — Amortized vs Worst-Case Cost over a Sequence

flowchart LR
    subgraph "Cost over a sequence of n pushes"
      direction TB
      P1["push 1: cost 1"]
      P2["push 2: cost 2 (resize 1)"]
      P3["push 3: cost 1"]
      P4["push 4: cost 3 (resize 2)"]
      P5["push 5–7: cost 1 each"]
      P8["push 8: cost 5 (resize 4)"]
      etc["..."]
    end

    Sum["Sum across n pushes ≤ 3n"]
    Avg["Amortized per push = 3 = O(1)"]

    P1 --> Sum
    P2 --> Sum
    P3 --> Sum
    P4 --> Sum
    P5 --> Sum
    P8 --> Sum
    etc --> Sum
    Sum --> Avg

What this diagram shows. The actual cost of each individual push to a dynamic array (on the left) varies wildly: most are 1, but the rare resize-pushes cost O(k) where k is the current size. Summing all costs across n pushes (the middle node) gives ≤ 3n because of the geometric doubling — every resize costs the current size, and 1 + 2 + 4 + 8 + ... + n/2 < 2n. Dividing by n gives the amortized per-push cost of 3 = O(1) (the right node). The amortized bound is a flat per-operation cost that hides the burstiness of the actual costs.

13. Common Interview Problems

Problem	Naive analysis	Amortized analysis	Method best suited
append to dynamic array	O(n) worst	O(1) amortized	Aggregate or Accounting
MULTIPOP on stack	O(n) worst	O(1) per op amortized	Aggregate
find and union in Union-Find	O(log n) worst	O(α(n)) amortized	Potential (Tarjan 1975)
decrease-key in Fibonacci Heap	O(log n) worst	O(1) amortized	Potential (Fredman & Tarjan 1987)
Splaying in Splay Tree	O(n) worst	O(log n) amortized	Potential (Sleator & Tarjan 1985)
n increments of binary counter	O(n) per worst inc	O(1) amortized	Aggregate

14. Open Questions

• Is there an amortized argument for Quicksort? No — quicksort’s O(n log n) is average-case over random pivots, not amortized over a sequence of operations on a persistent data structure. Different framework.
• When is amortized analysis the wrong tool? Real-time systems (need worst-case bounds), or when you’re analysing a single one-off operation rather than a long sequence.
• Why does Union-Find’s amortized bound involve the inverse Ackermann function? Because path compression compresses ancestor chains in a way that the recursive structure of the proof matches the levels of the Ackermann hierarchy. Tarjan 1975 is the original argument; CLRS Ch. 21.4 gives a modern presentation.

15. See Also

• Big-O Notation — the upper-bound notation we are amortizing
• Big-Omega and Big-Theta — sometimes amortized bounds are stated as Θ
• Union-Find — O(α(n)) amortized via path compression + union by rank
• Splay Tree — O(log n) amortized via potential-method analysis
• Fibonacci Heap — O(1) amortized decrease-key
• Binary Heap — O(n) build-heap is not amortized — it is a tighter aggregate analysis without the amortization framework
• Stack — canonical stack-with-MULTIPOP example
• Recurrence Relations, Master Theorem — different non-amortized analysis tool
• Space Complexity — amortized space is rarely discussed but exists in some contexts (e.g., persistent data structures)
• SWE Interview Preparation MOC