Amortized Reasoning Methods

**Amortized cost is a per-operation figure obtained by dividing a bound on a whole sequence's cost by the number of operations in that sequence.** Stating it that precisely matters, because nearly every misunderstanding of the term comes from losing track of what the words range over. The definition: an operation has amortized cost T(n) if, for *every* sequence of m operations performed on the structure, the total cost of the sequence is at most m · T(n). Read the quantifier carefully — *every* sequence. There is no probability, no notion of a typical input, no assumption about the order in which callers do things. An amortized bound is a worst-case statement; it is simply a worst-case statement about a sum rather than about a single term of that sum. ## Three bounds that get confused - **Worst-case per operation.** Every individual call finishes within the bound. This is the strongest of the three, and the only one you can build a hard per-call deadline on. - **Amortized.** The *total* over any sequence is bounded, so the average across the sequence is bounded. Individual calls may be dramatically more expensive; the promise is that they are rare enough that the sum still divides down to the stated figure. - **Average-case, and its close relative expected.** The cost averaged over an assumed probability distribution — either over the inputs, or over random choices the algorithm itself makes. If the real workload does not match the assumed distribution, or an adversary picks inputs after reading the code, the bound evaporates. A blunt way to keep them apart: an average-case bound can be *wrong for your workload*. An amortized bound cannot be wrong for your workload, because it assumed nothing about the workload. What an amortized bound can be is *insufficient* — it never promised anything about any one call, so if that is what you need, it is silent. ## Why the sum can be bounded when a term cannot The pattern behind every amortized bound is the same: cheap operations quietly accumulate an obligation, and one later operation discharges the whole accumulated obligation at once. Because the expensive operation can only fire after enough cheap ones have run, its cost is spread over them. Three standard techniques formalise that: - **Aggregate analysis.** Count the total work done across the whole sequence directly, by whatever categorisation makes the sum easy, then divide by the number of operations. It requires no bookkeeping but only works when the total is easy to count in one go. - **The accounting method.** Charge each operation an artificial price, higher than its real cost for cheap operations. The surplus is stored as *credits* on specific parts of the structure and spent later to pay for expensive work. The argument is valid only if you can show the credit balance never goes negative — that check is the whole proof, and skipping it is the classic way to "prove" a false bound. - **The potential method.** Define a function from the structure's state to a number — its stored energy — and define the amortized cost of an operation as its actual cost plus the change in potential. Summing telescopes: the total amortized cost bounds the total actual cost as long as the potential never drops below its starting value. It handles messy operation mixes where you cannot cleanly enumerate work by category. All three are proof techniques for the same claim. Which one you reach for is a matter of which makes the arithmetic and the invariant easiest to check. ## Where the bound is the wrong tool Amortized bounds are a *throughput* promise. If your system processes a batch and only the total time matters, an amortized bound answers the question exactly. If your system serves requests against a percentile latency target, or holds a lock while calling the operation, or runs under a hard real-time deadline, then a single expensive call is precisely the event you care about, and the amortized bound says nothing about it. In those settings you either need a structure with worst-case per-operation bounds, or you need to *de-amortize* — restructure so a slice of the expensive maintenance is done on every operation instead of all at once. ## What to say out loud When an interviewer pushes with "but I watched one call take a long time," the answer is not to defend the call. It is: "That is allowed and expected — the bound covers the sequence, and the sequence is still O(n). If you need a bound on that one call, amortized is the wrong guarantee to be quoting, and here is what I would use instead." That reply shows you know both what the bound says and what it does not.