Why Amortized Analysis: Smoothing Worst-Case Spikes
What This Concept Is
Amortized analysis bounds total cost over an operation sequence, usually from a stated initial state. It does not assume a random input distribution. An amortized constant bound allows individual expensive operations while limiting their aggregate frequency or available unpaid work.
Expected analysis averages over a probability space; worst-case per-operation analysis bounds each call. A structure can have expected amortized bounds, so the labels describe separate dimensions rather than mutually exclusive choices.
Why It Matters Here
A throughput guarantee is not a tail-latency guarantee. You must know the initial state, which operations are allowed and what unit of work is counted before interpreting a bound.
Concrete Examples
The append-only array lab starts empty, doubles capacity on a full buffer and
counts one unit per element write or old-element copy. The first nine actual
costs are [1,2,3,1,5,1,1,1,9]. A resize is expensive, but cumulative work
at any positive prefix n is less than 3n. This does not bound each append by 3.
For a stack with push/pop/multipop, each item can be removed once after being pushed. Starting empty, total popped items cannot exceed pushes. Starting with a million items for free changes the bound unless initial stored work is charged.
The lab's abstract slot counts exclude allocation initialization, garbage collection and elapsed time. Its Python implementation allocates zeroed slots; including that work changes constants and needs an explicit cost model, even though geometric growth still supports a constant amortized result.
Common Confusion / Misconceptions
An average measured over one trace is not a worst-sequence proof. Amortized O(1) does not mean every operation is fast. Nonempty initial states can contain unpaid future work. An operation family with deletions may invalidate an append-only resize argument.
How To Use It
Declare start state, allowed sequence, primitive costs and whether randomness is present. Record individual and cumulative cost. Prove a bound for every valid prefix, then state what timing measurements add and what they cannot establish. When latency matters, consider reserving capacity or incremental rebuilding under a separately derived contract.
Check Yourself
Can a deterministic structure have an amortized bound? What initial work is hidden by starting with a populated stack? Why does mean time not settle worst-call latency?
Mini Drill or Application
For the first nine array appends, sum the supplied costs and identify the worst call. Feedback: total 24; ninth call costs 9. The mean is 24/9, but the proven prefix bound is more general.
Read This Only If Stuck
CLRS: aggregate, accounting and potential methods. Focus on the operation model before the named technique.