Overview

Amortized analysis determines the average cost per operation over a worst-case sequence of operations on a data structure, without using probability. Even though a single operation may occasionally be expensive, amortized analysis shows that the average cost across all operations is small. The chapter presents three techniques — aggregate analysis, the accounting method, and the potential method — applying each to stack operations with MULTIPOP and binary counter INCREMENT. It culminates with a detailed analysis of dynamic tables that expand and contract, proving O(1) amortized cost per insertion and deletion.

Key Concepts

• Amortized vs. average-case analysis: Amortized analysis guarantees average performance per operation in the worst case over any sequence of operations. It does not use probability or assume anything about the input distribution — it is a worst-case guarantee on the total cost of n operations.

• Three techniques:

• Aggregate analysis: Compute an upper bound T(n) on the total cost of n operations; the amortized cost per operation is T(n)/n. All operations receive the same amortized cost.

• Accounting method: Assign different amortized costs (charges) to different operation types. Early operations may be overcharged, storing the excess as "credit" on objects; later operations spend this credit. The key invariant: total credit must remain nonnegative at all times.

• Potential method: Define a potential function Φ mapping data structure states to real numbers. The amortized cost of operation i is ĉ_i = c_i + Φ(D_i) − Φ(D_{i−1}). If Φ(D_n) ≥ Φ(D_0) for all n, total amortized cost upper-bounds total actual cost.

• Charges are for analysis only: Amortized costs and credits/potentials are analytical tools. They do not appear in the code or affect the algorithm's behavior.

• The potential function telescopes: Total amortized cost = total actual cost + Φ(D_n) − Φ(D_0). Choosing Φ(D_0) = 0 and ensuring Φ(D_i) ≥ 0 guarantees the upper bound.

• Load factor: For dynamic tables, α(T) = T.num / T.size measures how full the table is. Maintaining a constant lower bound on α ensures wasted space is bounded.

Algorithms and Techniques

1. Stack with MULTIPOP — All Three Methods

Setup: A stack supports PUSH (cost 1), POP (cost 1), and MULTIPOP(S, k) (pops min(k, s) items, cost = min(k, s), where s is stack size).

Aggregate analysis:

• Naive bound: Each MULTIPOP costs O(n), giving O(n²) for n operations.
• Tighter: Each item can be popped at most once per push. Total POPs (including within MULTIPOP) ≤ total PUSHes ≤ n. So total cost = O(n), amortized O(1) per operation.

Accounting method:

• Assign amortized costs: PUSH = 2, POP = 0, MULTIPOP = 0.
• On each PUSH, pay 1 for the actual push and place 1 credit on the item.