Amortized Analysis: Aggregate, Accounting, Potential
What This Concept Is
An amortized bound limits total work over every valid operation sequence under stated initial conditions. It does not need a probability distribution. A constant amortized append cost allows occasional linear-cost appends; a constant worst-case append bound would additionally prohibit those spikes.
Aggregate analysis bounds the total directly. Accounting assigns charges and keeps a nonnegative credit balance. Potential assigns a function Phi to state and defines amortized_i = actual_i + Phi_i - Phi_(i-1). Summing telescopes:
sum(actual) = sum(amortized) + Phi_initial - Phi_final.
If Phi_final>=Phi_initial for every prefix, amortized total upper-bounds actual total. Amortized and actual costs need not agree on the last operation, and the bound need not be tight. Independent structures' valid sequence bounds can be added; shared state or operations outside either contract require a fresh argument.
Why It Matters Here
Capacity planning often needs total throughput, while a latency deadline needs a bound for an individual operation. Confusing these questions makes a mathematically correct total-cost statement unusable as a per-request guarantee. Expected bounds additionally specify what is random; amortized and expected describe different dimensions.
Concrete Examples
Dynamic array: one explicit model throughout
Start empty with capacity 1. Before writing into a full array, double capacity and copy every existing element. A copy costs1 and the new write costs1. Allocation and element-construction costs are excluded. This is a teaching model, not Python's list growth policy.
For n>=1 appends let C be the smallest power of two at least n. Copied elements total 1+2+...+C/2=C-1; for C=1 this sum is empty and equals0. Total cost is n+C-1 < 3n. At n=16, copies 15,total 31,maximum append9; at n=17, copies 31,total 48,maximum append17. Growing by one copies n(n-1)/2 elements, giving quadratic total cost.
Accounting: charge3 per append. The credit balance after n operations is 3n-(n+C-1)=2n-C+1, nonnegative for every prefix, including the empty state. This explicitly covers startup instead of relying on a half-full-array assumption before the first append.
Potential: choose Phi=2*size-capacity+1. Initially Phi=0. A non-resizing append changes Phi by2, so amortized cost is3. For a resize from capacity k, old size is k and new size is k+1 with capacity 2k. Old Phi=k+1; new Phi=3; delta=2-k. Actual cost k+1 plus that delta is3 again. Thus actual total equals 3n-Phi_final, and Phi is nonnegative on every reachable append-only state. A deletion policy changes reachable states and needs its own potential analysis.
Counter and stack: count the operations consistently
Increment an initially zero binary counter m times with enough bits to represent m. Bit j flips floor(m/2^j) times. Total flips are the sum over j>=0, less than 2m for m>0 and at least m. One increment may flip many bits; total flips are Theta(m). Do not confuse the number of bits with the number of increments.
For an initially empty stack, charge one unit of call overhead plus one unit per element inserted or removed. Across m PUSH/POP/MULTIPOP calls, at most m insertions occur and each inserted element can be removed once. Total work is at most3m. Phi=stack size pays for removals: PUSH has amortized cost3; POP/MULTIPOP have amortized cost1, including empty calls. Other cost conventions are possible, but state them consistently.
Common Confusion / Misconceptions
- Amortized is stronger than the same per-operation worst-case bound. A worst-case bound of c for every operation implies the same amortized bound. The converse fails.
- Any nonnegative potential gives constant amortized costs. Nonnegativity supports the telescoping inequality; individual amortized costs still need to be bounded. Phi=0 does nothing to hide an expensive MULTIPOP.
- A final low average proves the theorem. The proof covers all valid prefixes; one measured sequence does not establish it.
- An append-only proof covers deletion and shrinking. Alternating insert/delete can cause repeated rebuilds under a bad shrinking policy. Re-prove the combined operation set and initial state.
How To Use It
Specify the operation set, initial state, cost units, and permitted sequences. Prove a total bound, a credit invariant, or a potential argument. Track worst single-operation cost separately. If random choices are present, state the source of randomness and the adversary model before using the word expected.
Transfer / Where This Shows Up Later
Dynamic tables, hash-table rebuilds, and more advanced structures need sequence arguments. Their implementation costs depend on allocation, element size, and concurrency. Later systems work must measure those omitted costs before translating an operation count into a latency commitment.
Check Yourself
- What is the doubling trace's initial potential? Zero with the stated +1 shift.
- Can a high-cost final append invalidate the total bound? No; compute the resulting potential and telescope.
- Why is a constant potential insufficient to amortize MULTIPOP? It cannot release saved credit.
- Why is an expected bound different? It averages over an explicitly specified random experiment rather than only over sequence positions.
Mini Drill or Application
Run Lab A for n=16 and17. Derive the outputs before execution. Then derive the +1 policy at n=17: copies 136,total 153,maximum 17. Explain why the two policies can have equal maximum cost at that prefix while their total costs differ.
Read This Only If Stuck
Use the amortized-analysis and dynamic-table topics in CLRS. MIT's dynamic-array lecture supplies an alternate presentation. Reconstruct the accounting argument with this lesson's initial state rather than mixing conventions.