Chapter 16: Amortized Analysis: Accounting, Potential, and Dynamic Tables

The three core techniques are aggregate analysis, the accounting method, and the potential method — illustrated throughout using stack operations and binary counter increments as running examples. Aggregate analysis computes the total cost T(n) of n operations and divides by n: for a stack supporting PUSH, POP, and MULTIPOP, each element can only be popped once per push, so the total cost is O(n) and the amortized cost per operation is O(1); similarly, bits in a binary counter flip with decreasing frequency at higher positions, yielding O(n) total flips and O(1) amortized cost per increment. The accounting method assigns hypothetical amortized costs to operations, overcharging some to build up credit that covers the cost of later expensive operations — for example, charging $2 per PUSH so that $1 covers the push itself and $1 stored on the element pays for its eventual pop, keeping total credit non-negative throughout. The potential method generalizes this by defining a potential function Φ(D) representing stored work in the data structure, where the amortized cost of each operation equals its actual cost plus the change in potential, ensuring that summed amortized costs upper-bound total actual costs as long as potential never drops below its initial value. These techniques are then applied to dynamic tables, where a table doubles in size upon becoming full and halves when the load factor drops below one quarter — with an accounting method charge of $3 per insert covering the insert itself and future copying costs, and a piecewise potential function handling both expansion and contraction, yielding O(1) amortized cost for all insert and delete operations.