Amortized Analysis

Amortized analysis bounds the cost of an operation across a worst-case sequence rather than in isolation: a worst-case guarantee with no probability anywhere, often confused with average-case analysis but nothing like it. The three interchangeable methods are the aggregate method (bound the total cost of the sequence, divide by n), the accounting or banker's method (assign amortized charges and bank the surplus as credit, keeping the balance nonnegative), and the potential method (a function Phi on the whole state, with amortized cost = actual cost + change in Phi, which telescopes to bound the true total). Worked on the binary counter, a stack with multipop, and the canonical dynamic array whose geometric doubling gives O(1) amortized append via Phi = 2*size - capacity, even though a single append can copy the whole array.