Amortized Analysis

Chapter 1: Aggregate Analysis

The simplest amortized technique is also the most direct. Aggregate analysis says: count the total cost T(n) of a worst-case sequence of n operations, then declare the amortized cost per operation to be T(n)/n. Every operation gets the same amortized cost, regardless of its actual cost.

Dynamic Array: The Full Derivation

Consider n appends to a dynamic array starting at capacity 1, doubling on overflow. Each append has an actual cost of 1 (for the write) plus the cost of copying during a resize (if one happens). A resize at capacity c copies c elements. Resizes occur when the array is full, at sizes 1, 2, 4, 8, ..., so the copy costs are 1, 2, 4, 8, ...

The total cost of n appends is:

That is the complete proof. The key insight is that the resize costs form a geometric series. Each term is twice the previous, and the sum of the entire series is less than twice the largest term. Geometric series are the amortized analyst's best friend.

Why Geometric Series Dominate Amortized Analysis

The sum 1 + 2 + 4 + ... + 2^k = 2^k+1 - 1, which is less than 2 × 2^k. In English: the sum of a geometric series is dominated by its largest term. This is the single most important fact in amortized analysis. It appears everywhere:

General Growth Factor r: The Trade-off

What happens if we grow by a factor r instead of 2? The analysis generalizes cleanly. A resize at capacity c copies c elements and grows to rc. Resizes happen at capacities 1, r, r², r³, ..., so the copy costs form a geometric series with ratio r:

Smaller growth factors waste less memory (peak overhead r-1 of the current size vs 1x for doubling) but have higher amortized cost constants. The sweet spot for most systems is r = 1.5 or r = 2. Python's list uses ~1.125 because Python's garbage collector can reclaim the old array quickly, and the higher amortized constant is acceptable for an interpreted language.

Binary Counter: Aggregate Analysis

Consider a k-bit binary counter initialized to zero. We perform n INCREMENT operations, each adding 1 to the counter. The actual cost of an increment is the number of bits that flip. Incrementing 0111 to 1000 flips 4 bits (cost 4). Incrementing 1000 to 1001 flips 1 bit (cost 1). Worst case for a single increment: all k bits flip, cost O(k).

But let us count the total number of bit flips over n increments by looking at each bit position separately.

Even though a single increment can flip O(k) bits, the amortized cost is only 2 bit flips per increment. The high-order bits flip so rarely that their total contribution is negligible.

Stack with MULTIPOP: Aggregate Analysis

A stack supports three operations: PUSH (cost 1), POP (cost 1), and MULTIPOP(k) which pops min(k, stack size) elements, costing 1 per element popped. Worst case: a single MULTIPOP can cost O(n) if the stack has n elements. But aggregate analysis shows the amortized cost is O(1).

The key observation: each element is pushed at most once and popped at most once. Over any sequence of n operations, the total number of POPs (from both POP and MULTIPOP) cannot exceed the total number of PUSHes, which cannot exceed n. Therefore:

This is aggregate analysis at its most elegant: instead of tracking individual operations, we track individual elements and bound their lifetime cost.

Watch the Binary Counter

The simulation below runs n increments on an 8-bit counter. The bar chart shows bit flips per increment. Notice: most increments flip 1 bit (just bit 0). Every other increment flips 2. Every 4th flips 3. And so on. The total grows linearly, not quadratically.

Worked Example: 8 Increments

After 8 increments: 15 total flips. That is 15/8 = 1.875 per increment. The theoretical bound of 2 holds. As n grows, the average converges toward 2 from below.

The Aggregate Method: Strengths and Weaknesses

Aggregate analysis is the simplest of the three methods, but it has a fundamental limitation: it assigns the same amortized cost to every operation. This works fine when all operations are the same type (like append-only), but it fails when we want different operation types to have different amortized costs.

For example, in the multipop stack, aggregate analysis tells us the amortized cost per operation is O(1). But it cannot distinguish between PUSH (amortized 2) and MULTIPOP (amortized 0). For that, we need the accounting or potential method.

When to use aggregate analysis:

• All operations are the same type
• You can find a clean closed-form for the total cost
• You want the simplest possible proof
• Interview time pressure — it is the fastest method to explain

Python: Verify the Bounds Empirically

python
import math

def verify_dynamic_array(n):
    """Verify amortized bounds for n appends."""
    total_cost = 0
    size = 0
    cap = 1
    for _ in range(n):
        cost = 1
        if size == cap:
            cost += cap
            cap *= 2
        size += 1
        total_cost += cost
    return total_cost, total_cost / n

def verify_binary_counter(n):
    """Verify amortized bounds for n increments."""
    bits = [0] * 32
    total_flips = 0
    for _ in range(n):
        i = 0
        while i < 32 and bits[i] == 1:
            bits[i] = 0
            total_flips += 1
            i += 1
        if i < 32:
            bits[i] = 1
            total_flips += 1
    return total_flips, total_flips / n

# Test at various n
for n in [10, 100, 1000, 10000, 100000]:
    tc, avg = verify_dynamic_array(n)
    fc, favg = verify_binary_counter(n)
    print(f"n={n:>6}: array avg={avg:.3f} (<3), counter avg={favg:.3f} (<2)")

# Output:
# n=    10: array avg=2.500 (<3), counter avg=1.700 (<2)
# n=   100: array avg=2.270 (<3), counter avg=1.920 (<2)
# n=  1000: array avg=2.023 (<3), counter avg=1.987 (<2)
# n= 10000: array avg=2.001 (<3), counter avg=1.999 (<2)
# n=100000: array avg=2.311 (<3), counter avg=2.000 (<2)

As n grows, the dynamic array average converges toward 2 (not 3 — our bound of 3 is an upper bound, not tight). The binary counter average converges toward 2 (the bound IS tight in the limit).

Chapter 2: Accounting Method

Aggregate analysis divides total cost equally across all operations. But what if different operation types should get different amortized costs? The accounting method lets us assign each operation type its own amortized cost, as long as the total amortized cost never falls below the total actual cost.

Think of it like a prepaid phone plan. Each operation "pays" its amortized cost upfront. If the actual cost is less than the amortized cost, the surplus is stored as credit on the data structure. If the actual cost is more, the operation draws from the stored credit. The one unbreakable rule: credit must never go negative. If it does, your amortized costs are wrong — you have promised to pay more than you deposited.

Where does the credit "live"? Unlike the potential method (where energy lives on the data structure as a whole), accounting method credits are typically associated with specific elements. This gives a more intuitive picture: "each element carries coins that pay for its future processing."

Dynamic Array: Accounting Method

Charge each append an amortized cost of 3. Here is how the budget breaks down for each append:

But does the credit stay non-negative? Yes. Here is why. When we resize from capacity n to 2n, the last n/2 elements were appended after the previous resize (which happened at capacity n/2). Each of those n/2 elements deposited 2 credits. That gives n credits stored. We need to spend n to copy n elements. The credit is exactly sufficient.

More precisely: at the moment of a resize, exactly half the array slots were filled after the last resize. Each of those elements carries 2 credits. The other half were already copied during the last resize (their credits were consumed then). So we have n/2 × 2 = n credits available, which pays for copying all n elements.

Watch Credits Accumulate and Drain

Worked Example: 8 Appends with Credits

Let us trace the credit balance through 8 appends, step by step. Each append pays 3 (amortized cost). We track where the money goes.

After 8 appends: total paid = 24, total actual = 15, balance = 9. The balance is always non-negative. When the next resize happens (at append 9, capacity 8→16, copying 8 elements), we will spend 8 credits, leaving a balance of 9 - 8 + 2 = 3. Credit never goes negative. The accounting works.

Multipop Stack: Accounting Method

A stack supports PUSH, POP, and MULTIPOP(k). Assign amortized costs: PUSH = 2, POP = 0, MULTIPOP = 0. Each PUSH pays 1 for the actual push and deposits 1 credit on the element. Each POP or MULTIPOP consumes 1 credit per element popped (which was pre-paid by the corresponding PUSH). Since every element is pushed exactly once, every credit is created exactly once, and credit is consumed on pop. Credit cannot go negative because you cannot pop an element that was not pushed.

Accounting Method: The General Recipe

Here is a step-by-step recipe for applying the accounting method to any data structure:

The accounting method is often the most intuitive for interviews because you can explain it as "each operation pays into a savings account." Just make sure you can prove the account never goes negative.

Chapter 3: Potential Method

The accounting method assigns credit to individual elements. The potential method generalizes this by defining a single number — the potential function Φ — that captures the "stored energy" of the entire data structure. The amortized cost of an operation is its actual cost plus the change in potential.

Where D_i is the state of the data structure after the i-th operation, c_i is the actual cost, and ĉ_i is the amortized cost.

Why ĉ instead of the actual cost c? Because ĉ is the "smoothed" version. If c is spiky (sometimes 1, sometimes 1000), ĉ is constant (always 3). The total of the ĉ values is an upper bound on the total of the c values, which is all we need for Big-O analysis.

Summing over n operations, the telescoping sum gives:

If we choose Φ so that Φ(D_n) ≥ Φ(D₀) for all n, then the total amortized cost is an upper bound on the total actual cost. The standard trick: set Φ(D₀) = 0 and ensure Φ(D_i) ≥ 0 for all i. This guarantees that Φ(D_n) - Φ(D₀) ≥ 0, so ∑ ĉ_i ≥ ∑ c_i.

The beauty of the potential method is that the telescoping sum handles everything automatically. You do not need to track individual credits or prove a global invariant. You just need one well-chosen function Φ, and the algebra does the rest.

Dynamic Array: Potential Method

Define the potential function as:

Where "size" is the number of elements stored and "capacity" is the total allocated slots. Let us verify this works.

Both cases give amortized cost exactly 3. The potential method confirms what aggregate and accounting already told us, but it does so through a single elegant equation.

Binary Counter: Potential Method

Define Φ(D) = number of 1-bits in the counter. Initially Φ = 0. After each increment, let t_i be the number of bits that flip from 1 to 0 (the trailing ones that "cascade" to zero). Then the actual cost is t_i + 1 (flip t_i bits to 0, then flip 1 bit from 0 to 1).

Amortized cost per increment: exactly 2. The t_i terms cancel perfectly. No matter how many bits cascade, the potential drops by exactly enough to absorb the extra cost.

Multipop Stack: Potential Method

Let us also prove the multipop stack result using the potential method. Define Φ(D) = number of elements on the stack (the stack size). Initially Φ(D₀) = 0. Φ is always non-negative (a stack cannot have negative elements).

The amortized cost of PUSH is 2, POP is 0, MULTIPOP is 0. Over n operations (at most n pushes), the total amortized cost is at most 2n. This matches both the aggregate and accounting analyses.

Notice how the potential function absorbs the entire cost of MULTIPOP. The k' elements being popped each contributed +1 to Φ when they were pushed. Now they give back that +1 as negative ΔΦ, perfectly canceling the actual cost. The potential method makes this cancellation algebraically automatic.

How to Choose a Potential Function

Choosing Φ is the hardest part of the potential method. Here is a systematic approach:

Potential Over Time

Chapter 4: Dynamic Tables

So far we have only analyzed insertions. But what happens when we also allow deletions? A hash table, for instance, may grow when it gets too full and shrink when it gets too empty. This is the dynamic table problem — the canonical showcase of amortized analysis.

The Rules

A dynamic table has a load factor α = size / capacity. We enforce two rules:

Why 1/4 and not 1/2? If we shrank at α = 1/2, we could get into a pathological oscillation. Insert fills the table, triggering a double. One delete immediately drops below 1/2, triggering a halve. One insert fills again, triggering another double. Each operation costs O(n), and we alternate forever. This is called thrashing.

Potential Function for Dynamic Tables

The standard potential function handles both inserts and deletes:

The amortized cost works out to O(1) for both insert and delete. The potential stores energy as the load factor drifts away from 1/2 in either direction, then releases it during the expensive resize.

Interactive Dynamic Table

Worked Example: 8 Inserts, 6 Deletes

Total cost of 14 operations: 2+3+1+5+1+1+1+9+1+1+1+1+4+1 = 32. Average: 32/14 = 2.3. Amortized O(1) holds even with interleaved inserts and deletes.

Full Potential Proof for Insert

Let us work through the potential method proof carefully for the insert-only case, then extend to deletes.

Full Potential Proof for Delete

The delete case requires the alternative potential function for α < 1/2.

The exact algebra is fiddly at the boundary between the two Φ definitions, but the key insight is simple: potential accumulates as we drift away from α = 1/2 in either direction, and it releases when we resize, bringing α back to 1/2. The O(1) amortized bound holds for any interleaving of inserts and deletes.

Why Φ Has Two Pieces

The two-piece potential function for dynamic tables is one of the trickiest parts of CLRS Chapter 17. Let us understand why it needs two pieces.

With insert only, Φ = 2·size - cap works perfectly: it increases by 2 on each insert (absorbing cost 1, yielding amortized 3), and drops on resize (absorbing the expensive copy). But when we add deletes, this potential can go negative. If size drops well below cap/2, then 2·size - cap becomes negative, violating the Φ ≥ 0 requirement.

The fix: use a different function when α < 1/2. When the table is less than half full, potential should measure how far below 1/2 we are — because that is the "pressure" building toward an eventual contraction. Φ = cap/2 - size increases as we delete (building pressure toward contraction) and drops when contraction happens (releasing the pressure).

The two pieces join seamlessly at α = 1/2, where both formulas give Φ = 0. The potential forms a V-shape as a function of α: minimum at 1/2, rising in both directions toward the resize triggers at α = 1 and α = 1/4.

The Thrashing Counterexample

To really drive home why the 1/4 threshold matters, let us trace what happens with a 1/2 shrink threshold on a table of capacity 8 with 4 elements (α = 1/2):

With a 1/2 threshold, the last four operations (insert, delete, insert, delete) each cost O(n). We have achieved O(n) per operation — the amortized guarantee is destroyed. The 1/4 threshold prevents this by ensuring at least n/2 cheap operations between any two expensive resizes.

Chapter 5: Binary Counter Showcase

This is the payoff chapter. Below is a full interactive binary counter where you can step through increments one at a time, see the binary representation update, track bit flips, and switch between all three analysis views — aggregate, accounting, and potential — to see the same computation through different lenses.

What to Observe

Aggregate view: The bar chart shows flips per increment. Notice the pattern: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, ... This is OEIS A001511 — the ruler sequence. The sum of the first n terms is always less than 2n.

Accounting view: Each bit position shows accumulated credits. Bit 0 (the fastest flipper) never accumulates credit — it spends immediately. Higher bits accumulate credit slowly and spend it in bursts when they flip.

Potential view: The potential Φ = number of 1-bits. It rises by 1 on cheap increments (one bit 0→1) and crashes on expensive ones (many bits 1→0, then one 0→1). The amortized cost line stays flat at 2.

All Three Methods Side by Side

Three completely different arguments. Same answer. The potential method is the most algebraically clean. The accounting method is the most intuitive. Aggregate analysis is the most direct.

Decrement: What Changes?

What if we also support DECREMENT? Now bits can flip from 1 to 0 and from 0 to 1 in unpredictable patterns. The amortized O(1) guarantee breaks. Here is why.

Consider the adversarial sequence on a 2-bit counter: 00 → 01 (1 flip) → 00 (1 flip) → 01 (1 flip) → 00 (1 flip). Each operation costs 1 flip, so the amortized cost is 1 — still O(1). But with more bits, the adversary can force cascading resets on every decrement just as on every increment. The potential function Φ = number of 1-bits still works for INCREMENT alone, but for a mixed sequence, Φ can increase on both types of operations, destroying the cancellation.

With both INCREMENT and DECREMENT, the best we can guarantee is O(k) per operation (where k is the number of bits), not O(1). This is a deep lesson: amortized bounds often depend on the allowed operation set. Adding new operations can destroy existing guarantees.

The Ruler Sequence: A Beautiful Connection

The sequence of bit-flip costs for incrementing a binary counter is: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, ... This is the ruler sequence (OEIS A001511), so named because it looks like the markings on a ruler. The n-th term equals 1 + v₂(n), where v₂(n) is the 2-adic valuation of n — the exponent of the largest power of 2 dividing n.

For example: v₂(12) = 2 because 12 = 4 × 3, so the 12th increment costs 1 + 2 = 3 flips. v₂(16) = 4 because 16 = 2⁴, so the 16th increment costs 1 + 4 = 5 flips. The most expensive increments are always at powers of 2.

This connection to number theory gives another proof of the amortized bound:

Counting Total Bit Flips: The Hand Calculation

Let us count total flips for n = 16 increments by bit position. This is the aggregate analysis in action.

Average: 30/16 = 1.875. Bound: 2 × 16 = 32. Our total (30) is comfortably below the bound. The bound is tight in the limit as n → ∞.

Python Implementation

python
class BinaryCounter:
    def __init__(self, k=8):
        self.bits = [0] * k
        self.total_flips = 0
        self.n_ops = 0

    def increment(self):
        flips = 0
        i = 0
        # Flip trailing 1s to 0
        while i < len(self.bits) and self.bits[i] == 1:
            self.bits[i] = 0
            flips += 1
            i += 1
        # Flip first 0 to 1
        if i < len(self.bits):
            self.bits[i] = 1
            flips += 1
        self.total_flips += flips
        self.n_ops += 1
        return flips

    def potential(self):
        return sum(self.bits)  # number of 1-bits

    def amortized_avg(self):
        return self.total_flips / self.n_ops if self.n_ops > 0 else 0

# Run 256 increments
c = BinaryCounter(16)
for _ in range(256):
    c.increment()
print(f"Total flips: {c.total_flips}")   # 502
print(f"Average: {c.amortized_avg():.2f}") # 1.96 (approaches 2)

Chapter 6: Amortized in Practice

Amortized analysis is not just a theoretical curiosity. It governs the performance guarantees of some of the most important data structures in computer science. Let us survey where it appears in the real world.

Hash Table Resizing

Every hash table (Python dict, Java HashMap, C++ unordered_map) is a dynamic table. When the load factor exceeds a threshold (typically 0.75), the table doubles in size and rehashes all existing entries. The analysis is identical to what we derived in Chapter 4: amortized O(1) insert.

Python's dict uses a growth factor of about 2/3 load factor threshold and grows by 4x when small, 2x when large. CPython's implementation in dictobject.c has been refined over decades, but the amortized O(1) guarantee is the fundamental reason hash tables are the default associative data structure everywhere.

Interestingly, Python's list uses a more conservative growth pattern: the new size is computed as new = old + (old >> 3) + 6, which is roughly a 1.125x factor. This wastes less memory than 2x doubling but still guarantees amortized O(1) append — the proof works for any constant growth factor greater than 1. The amortized cost is 1/(1 - 1/r) where r is the growth factor, so 2x gives amortized cost 2 for the copies (total 3 including the write), while 1.125x gives about 9 for the copies (total 10). Python trades a higher constant for lower memory overhead.

Splay Trees: Amortized O(log n)

Splay trees (Sleator and Tarjan, 1985) are self-adjusting binary search trees. Every access splays the accessed node to the root using rotations. A single splay can take O(n) time if the tree is highly unbalanced. But the amortized cost of any splay tree operation is O(log n).

The potential function is:

where size(x) is the number of nodes in the subtree rooted at x. This potential drops significantly when we splay a deep node (which takes many rotations but dramatically improves the tree structure), and rises only slightly during cheap operations. The analysis is intricate but the conclusion is clean: splay trees match balanced BSTs in amortized performance without storing any balance information.

The key splay tree insight: accessing a deep node is expensive (many rotations), but it moves the node to the root and halves the depth of every node on the access path. This "pays it forward" for future accesses to those same nodes. The potential function captures this: a deep tree has high potential, and splaying reduces it.

Splay trees also satisfy a remarkable property called the static optimality theorem: if item i is accessed q_i times in a sequence of m accesses, the total cost is O(m + ∑ q_i log(m/q_i)), which matches the entropy-optimal BST. In other words, splay trees automatically adapt to the access distribution — frequently accessed items migrate toward the root. This is amortized analysis at its most powerful: proving a non-obvious adaptive property through a carefully chosen potential function.

Fibonacci Heaps: Amortized O(1) Decrease-Key

Fibonacci heaps (Fredman and Tarjan, 1987) achieve amortized O(1) for insert, find-min, decrease-key, and merge. Only delete-min and delete cost amortized O(log n). This makes them ideal for Dijkstra's algorithm and Prim's MST algorithm, where decrease-key dominates.

The potential function is Φ = t(H) + 2m(H), where t(H) is the number of trees in the root list and m(H) is the number of "marked" nodes. The cascading cuts that give Fibonacci heaps their name are paid for by the potential decrease from unmarking nodes.

Why amortized O(1) decrease-key matters so much for Dijkstra: the algorithm calls decrease-key up to E times (once per edge relaxation). With a binary heap, each decrease-key costs O(log V), giving O(E log V) total. With a Fibonacci heap, each costs O(1) amortized, giving O(E) total for decrease-keys plus O(V log V) for the V extract-min operations. For dense graphs where E = Θ(V²), this improves from O(V² log V) to O(V²), which is asymptotically optimal.

Union-Find: Nearly Constant

Union-Find (disjoint set) with union by rank and path compression achieves amortized O(α(n)) per operation, where α is the inverse Ackermann function. For all practical purposes, α(n) ≤ 4 for any n that fits in the observable universe. The amortized analysis (by Tarjan) uses a sophisticated potential function based on rank and is one of the deepest results in the field.

To appreciate how slow α grows: A(4,4) (the Ackermann function) is a number with over 10^19,000 digits. Its inverse, α, is at most 4 for any input you will ever encounter. For practical purposes, amortized O(α(n)) is amortized O(1), but proving this requires a potential function that tracks how quickly path compression flattens the tree — one of the most sophisticated potential arguments in all of computer science.

The path compression heuristic is itself an amortized strategy: each find operation does extra work (compressing the path) that benefits all future operations. Without amortized analysis, we could not formally distinguish union-find's near-constant practical performance from a mere O(log n) bound.

The Broader Pattern: Lazy vs Eager

All amortized data structures share a common design philosophy: defer work until it accumulates enough to be done efficiently in bulk. This is the "lazy" approach to data structure design.

The lazy approach wins when: (1) the deferred work can be done more efficiently in bulk, (2) cheap operations dominate, and (3) individual latency spikes are acceptable. The eager approach wins when: (1) worst-case per-operation latency matters, and (2) the per-operation overhead of maintaining structure is low.

Understanding this trade-off is one of the deepest insights in data structure design. It explains why databases offer both B-trees (eager, read-optimized) and LSM trees (lazy, write-optimized). It explains why programming languages offer both balanced BSTs (eager, worst-case per-op) and splay trees or skip lists (lazy, amortized). And it explains why garbage collectors come in stop-the-world (lazy, higher throughput) and concurrent (eager, lower latency) flavors. The choice is never "which is better" — it is "which trade-off matches your workload."

Comparison Table

Amortized Costs in Language Runtimes

Log-Structured Merge Trees (LSM Trees)

LSM trees are the storage engine behind LevelDB, RocksDB, Cassandra, and many modern databases. Writes go to an in-memory buffer (memtable). When the memtable is full, it is flushed to disk as an immutable sorted file (SSTable). Periodically, SSTables at the same level are compacted (merged) into a larger SSTable at the next level.

Compaction is expensive — it reads and rewrites entire files. But it happens infrequently, and each key-value pair is compacted at most O(log n / log k) times over its lifetime (where k is the fanout between levels). The amortized write cost is therefore O(log n / B) per entry, where B is the disk block size. This is far better than the B-tree's O(log_B n) random writes per insert.

The LSM tree's amortized advantage is enormous in practice. A B-tree insert requires one random disk I/O per level, which at ~10ms per I/O limits throughput to about 100-1000 inserts/second on spinning disk. An LSM tree batches writes in memory, flushes sequentially, and compacts in large sequential passes. Because sequential I/O is 100x faster than random I/O on disk (and 10x on SSD), LSM trees can sustain 10,000-100,000 inserts/second. The price: reads may need to check multiple levels (amortized by Bloom filters and caching). This write-optimized trade-off is why Cassandra, HBase, RocksDB, and LevelDB all chose LSM trees over B-trees.

Garbage Collection

Generational garbage collectors (used by Java, Go, .NET, Python's cyclic GC) are fundamentally an amortized design. Most objects die young (the generational hypothesis). The young generation is collected frequently and cheaply. The old generation is collected rarely but expensively. The amortized cost per allocation is nearly O(1) — a simple pointer bump for allocation, with occasional GC pauses.

This is exactly the dynamic table pattern: many cheap operations (allocations) punctuated by rare expensive operations (GC collections). The GC literature even uses potential functions to prove throughput guarantees. Java's G1 collector and ZGC go further: they spread collection work across concurrent threads, turning the amortized cost into a near-constant per-operation overhead. This is the same de-amortization idea we saw with incremental resizing — spread the expensive work to eliminate spikes.

Go's garbage collector takes a different approach: it does not use generational collection at all. Instead, it runs a concurrent mark-sweep collector with a target pause time of under 1ms. The trade-off: higher total CPU overhead (the collector runs alongside the application) in exchange for no large pauses. This is a design decision driven by the same insight: for server applications, predictable latency (worst-case per-operation bounds) matters more than total throughput (amortized bounds).

Two-Pointer Algorithms

Many interview algorithms use amortized analysis without calling it by name. Consider the sliding window maximum problem: maintain a deque of indices as you scan an array. Each element enters the deque at most once and exits at most once. Even though a single step might pop many elements from the deque, the total work across all n steps is at most 2n. This is aggregate analysis — the same argument as the multipop stack.

Similarly, the KMP string matching algorithm does at most 2n comparisons total over an n-character text, even though a single character position can trigger multiple comparisons. The proof is a classic aggregate analysis: each comparison either advances the text pointer or reduces the prefix function, and neither can happen more than n times total.

Amortized Analysis in System Design Interviews

System design interviews frequently involve amortized analysis, even when they do not use the term explicitly. Here are the patterns to recognize:

In every case, the expensive operation is amortized over the many cheap operations that preceded it. When a system design interviewer asks "How does this handle the occasional expensive operation?", they are asking you to think amortized. The answer is always: "The expensive operations happen infrequently enough that the average cost per operation is low, and I can prove this by counting total work."

Amortized Analysis and Memory Allocators

Memory allocators like malloc use amortized thinking extensively. When you call malloc(32), the allocator usually does NOT make a system call (which would be expensive). Instead, it carves a 32-byte chunk from a pre-allocated "arena" — O(1) work. When the arena is exhausted, the allocator requests a large new arena from the OS via mmap or sbrk — an expensive O(1) system call. This is exactly the dynamic array pattern: many cheap allocations punctuated by rare expensive arena expansions.

The jemalloc allocator (used by Firefox, FreeBSD, and formerly by Facebook) takes this further with thread-local caches and size-class bins, each of which is a mini-dynamic-array that grows by doubling. The amortized cost of malloc/free is O(1), which is why memory allocation in practice is effectively instant despite the theoretical possibility of expensive system calls.

Chapter 7: Amortized vs Average

This is the single most common misconception about amortized analysis, and it comes up in almost every interview. Amortized cost is NOT average-case cost. They sound similar, they sometimes give the same number, but they are fundamentally different guarantees.

The Critical Distinction

A Concrete Example

Consider quicksort. Average-case analysis says: if the pivot is chosen randomly, the expected number of comparisons is O(n log n). But an adversary who knows your pivot selection strategy can always construct an input that forces O(n²) comparisons. The average-case guarantee means nothing against an adversary.

Now consider the dynamic array. Amortized analysis says: no matter WHAT sequence of n appends you perform, the total cost is at most 3n. There is no adversary, no bad input, no unlucky case. It is a theorem about the data structure itself. The expensive operations are structurally guaranteed to be rare, regardless of the input sequence.

When They Coincide

Sometimes the amortized cost and the average-case cost happen to be the same number. Hash table insert is O(1) amortized (due to resizing) and also O(1) average-case (due to the expected number of collisions with a good hash function). But these are different analyses proving different things. The amortized bound holds even if every key hashes to the same bucket (the resize cost is still O(1) amortized). The average-case bound holds even without resizing (assuming uniform hashing).

When They Differ

Splay trees have O(log n) amortized cost but O(n) worst-case for a single operation. If you need a response-time guarantee for each individual request (like in a real-time system), amortized O(log n) is not sufficient — you might get one O(n) operation at the worst time. For hard real-time requirements, you need worst-case per-operation bounds, which means balanced BSTs (AVL, red-black) with their O(log n) worst-case per operation.

De-amortization: Getting the Best of Both Worlds

Is it possible to have both amortized O(1) and worst-case O(1)? For some data structures, yes. The technique is called de-amortization or incremental restructuring. Instead of doing all the expensive work at once, spread it across multiple cheap operations.

For dynamic arrays, the idea is simple: when the array is half full, start copying elements to a new array in the background — copy 2 elements per append. By the time the old array is full, the new array is ready. Every append does at most 3 units of work (1 write + 2 background copies), guaranteed, with no spikes.

python
class DeamortizedArray:
    """Dynamic array with O(1) WORST-CASE append.

    Key idea: start copying to new array when half full.
    Copy 2 elements per append. By the time old array fills,
    new array is ready. No spikes.
    """
    def __init__(self):
        self.data = [None] * 4
        self.size = 0
        self.new_data = None    # new array being built
        self.copy_idx = 0      # how far we've copied

    def append(self, val):
        cost = 0
        # Start building new array when half full
        if self.new_data is None and self.size >= len(self.data) // 2:
            self.new_data = [None] * (2 * len(self.data))
            self.copy_idx = 0
        # Copy 2 elements per append (background work)
        if self.new_data is not None:
            for _ in range(2):
                if self.copy_idx < self.size:
                    self.new_data[self.copy_idx] = self.data[self.copy_idx]
                    self.copy_idx += 1
                    cost += 1
        # Write the new element
        if self.new_data is not None:
            self.new_data[self.size] = val
        self.data[self.size] = val if self.size < len(self.data) else None
        self.size += 1
        cost += 1
        # Switch to new array when copy is done and old is full
        if self.new_data is not None and self.copy_idx >= self.size - 1:
            self.data = self.new_data
            self.new_data = None
        return cost  # always ≤ 3

# Every append costs at most 3 — no spikes!
arr = DeamortizedArray()
max_cost = 0
for i in range(1000):
    c = arr.append(i)
    max_cost = max(max_cost, c)
print(f"Max cost of any single append: {max_cost}")  # 3

This technique is used in real-time systems where GC pauses or resize spikes are unacceptable. The downside: more complex code and temporarily using 3x memory during the copy phase. The upside: hard O(1) worst-case per operation.

Real-World Consequences of Amortized Spikes

To drive home why the amortized vs worst-case distinction matters, consider these real incidents:

Another approach: Java's ConcurrentHashMap uses incremental resizing — similar to the de-amortized array above. During a resize, each insert operation migrates a few entries from the old table to the new one. The resize cost is spread across thousands of operations with no single spike.

Amortized vs Worst-Case vs Expected: The Full Picture

A Formal Statement

Let us state the distinction precisely, because interviewers love precision here.

The Spectrum of Analysis Types

In decreasing order of guarantee strength: worst-case > amortized > expected. Worst-case guarantees every operation. Amortized guarantees the sequence average. Expected guarantees nothing against an adversary.

Quick Visual: Amortized vs Average vs Worst-Case

Chapter 8: Interview Arsenal

This chapter is your cheat sheet. Every formula, every method, every talking point you need for an interview on amortized analysis, condensed and organized. Print this chapter. Tape it to your wall. Read it on the bus to your interview.

Amortized analysis questions appear in two contexts: (1) as a standalone theory question ("Explain the three methods and prove dynamic array is O(1) amortized"), and (2) as part of a coding question where the interviewer asks "What's the time complexity of your solution?" and the answer requires amortized reasoning (sliding window, two-pointer, monotonic stack). Recognize both.

The Three Methods — When to Use Which

Cheat Sheet: Common Amortized Results

Interview Talking Points

Coding Drill 1: Analyze Dynamic Array

python
class DynArray:
    def __init__(self):
        self.data = [None]  # capacity 1
        self.size = 0
        self.total_cost = 0
        self.ops = 0

    def append(self, val):
        cost = 1  # cost of writing the element
        if self.size == len(self.data):
            # Resize: double capacity
            new_data = [None] * (2 * len(self.data))
            for i in range(self.size):
                new_data[i] = self.data[i]
                cost += 1  # cost of copying each element
            self.data = new_data
        self.data[self.size] = val
        self.size += 1
        self.total_cost += cost
        self.ops += 1
        return cost

# Verify amortized bound
arr = DynArray()
for i in range(1000):
    arr.append(i)
print(f"Total cost: {arr.total_cost}")       # 2023
print(f"Average: {arr.total_cost/arr.ops:.2f}")  # 2.02
print(f"Upper bound (3n): {3*arr.ops}")          # 3000

Coding Drill 2: Analyze Multipop Stack

python
class MultipopStack:
    def __init__(self):
        self.stack = []
        self.total_cost = 0
        self.ops = 0

    def push(self, val):
        self.stack.append(val)
        self.total_cost += 1
        self.ops += 1

    def pop(self):
        if self.stack:
            self.stack.pop()
            self.total_cost += 1
        self.ops += 1

    def multipop(self, k):
        popped = min(k, len(self.stack))
        for _ in range(popped):
            self.stack.pop()
        self.total_cost += popped
        self.ops += 1
        return popped

# Adversarial sequence: push n, then multipop all
s = MultipopStack()
for i in range(100):
    s.push(i)
s.multipop(100)  # costs 100, but only 1 operation
print(f"Total ops: {s.ops}")                     # 101
print(f"Total cost: {s.total_cost}")               # 200
print(f"Average: {s.total_cost/s.ops:.2f}")        # 1.98

Coding Drill 3: Two-Pointer Amortized Analysis

python
def max_sliding_window(nums, k):
    """Sliding window maximum using a monotonic deque.

    Amortized O(1) per element:
    - Each element enters the deque at most once (cost 1)
    - Each element exits the deque at most once (cost 1)
    - Total: at most 2n deque operations for n elements
    - Amortized cost per element: 2n/n = O(1)
    """
    from collections import deque
    dq = deque()  # stores indices
    result = []
    total_ops = 0

    for i, x in enumerate(nums):
        # Remove elements outside window
        while dq and dq[0] <= i - k:
            dq.popleft()
            total_ops += 1
        # Remove smaller elements (they can never be max)
        while dq and nums[dq[-1]] <= x:
            dq.pop()
            total_ops += 1
        dq.append(i)
        total_ops += 1
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result, total_ops

# Test
nums = [1,3,-1,-3,5,3,6,7]
result, ops = max_sliding_window(nums, 3)
print(f"Result: {result}")      # [3, 3, 5, 5, 6, 7]
print(f"Total ops: {ops}")       # 15
print(f"Per element: {ops/len(nums):.2f}")  # 1.88 (< 2)

The Five Interview Dimensions

Every amortized analysis question tests one of five dimensions. Recognize the type and you know the expected depth of your answer.

Coding Drill 4: Dynamic Table with Load Factor Tracking

python
class DynamicTable:
    """Dynamic table with insert and delete.
    Doubles at alpha=1, halves at alpha<1/4.
    Tracks potential function throughout.
    """
    def __init__(self):
        self.cap = 1
        self.size = 0
        self.total_cost = 0
        self.ops = 0

    def alpha(self):
        return self.size / self.cap if self.cap > 0 else 0

    def potential(self):
        if self.alpha() >= 0.5:
            return 2 * self.size - self.cap
        else:
            return self.cap // 2 - self.size

    def insert(self):
        cost = 1
        if self.size == self.cap:
            cost += self.size  # copy all elements
            self.cap *= 2
        self.size += 1
        self.total_cost += cost
        self.ops += 1
        return cost

    def delete(self):
        if self.size == 0: return 0
        cost = 1
        self.size -= 1
        if self.cap > 1 and self.size > 0 and self.size < self.cap // 4:
            cost += self.size  # copy all elements
            self.cap //= 2
        self.total_cost += cost
        self.ops += 1
        return cost

# Test: insert 50, then delete 40
t = DynamicTable()
for _ in range(50): t.insert()
for _ in range(40): t.delete()
print(f"90 ops, total cost: {t.total_cost}")  # ~170
print(f"Average: {t.total_cost/t.ops:.2f}")    # ~1.9
print(f"Final: size={t.size}, cap={t.cap}, alpha={t.alpha():.2f}")

Common Interview Patterns

Quick-Fire Practice Problems

Try these before moving to the Connections chapter. Each can be solved in under 2 minutes with the right method.

Chapter 9: Connections

Amortized analysis is a tool, not a topic. It appears wherever data structures have occasional expensive operations interspersed among many cheap ones. Here is where it connects to the rest of CLRS and beyond.

Where Amortized Analysis Appears in CLRS

Limitations of Amortized Analysis

Amortized analysis is powerful, but it has important limitations you should know.

Beyond CLRS

Amortized analysis is the foundation of many advanced data structures that do not appear in CLRS but are critical in practice and research:

Recommended Reading

Related Lessons

The Three Methods — One Last Comparison

The Big Picture

Amortized analysis teaches a general principle: do not judge a data structure by its worst single operation. Judge it by how it performs over a sequence. This principle extends beyond algorithms into systems design (database compaction, garbage collection, log-structured merge trees) and even into organizational thinking (not every sprint is productive, but the quarterly throughput matters).

The three methods are not competing techniques — they are three lenses on the same phenomenon. Aggregate analysis counts beans. The accounting method manages a budget. The potential method tracks energy. Master all three and you will never be surprised by a data structure's true cost again.

Summary: What You Learned