Start — a coffee punch card. Every tenth coffee on the card is "free." But nothing is really free: the shop quietly built a little extra into the price of the first nine, so the rare free cup was already paid for. Amortized analysis is exactly this trick turned into math. A few operations are occasionally very expensive, but if many cheap operations each chip in a little, the rare big cost is covered — and the average cost per operation stays small.
Build — a notebook that keeps filling up. Imagine a growable list (a Java ArrayList or C++ vector). When it fills, you copy everything into a notebook twice as big and keep going. Call the real cost of operation $i$ its actual cost $c_i$. Most inserts cost $1$; but each time the list doubles — at sizes $1, 2, 4, 8, \dots$ — you pay to copy. Inserting $n$ items, those copies total $1+2+4+\cdots+n < 2n$. So the whole job costs under $3n$ steps, and the amortized cost per insert is $3n/n = 3 = O(1)$. Concretely, building a list of $8$ items takes $8$ placements plus $1{+}2{+}4 = 7$ copies $= 15$ steps — under $3$ per item, even though one of those steps was eight times costlier than its neighbours.
Deepen — the potential method. The slick way to prove this uses a "savings account" called a potential function $\Phi(D) \ge 0$ that measures stored-up work in the structure $D$. Define the amortized cost of operation $i$ as $\hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$. Summing over a whole sequence telescopes: $\sum \hat c_i = \sum c_i + \Phi(D_n) - \Phi(D_0)$, so as long as $\Phi(D_n) \ge \Phi(D_0)$ the amortized total is an honest upper bound on the real total. For the doubling array, $\Phi = 2\,(\text{size}) - (\text{capacity})$ works: an ordinary insert raises $\Phi$ by $2$, giving $\hat c = 1 + 2 = 3$; a resize insert spends the $\Phi$ it had banked to pay for the $O(\text{size})$ copy and still nets out to $O(1)$. Splay trees use the same idea with $\Phi = \sum_x \log(\text{size}(x))$ to reach $O(\log n)$ amortized per access.
Try this in the sim above. The panel steps through a sequence of operations while the Operations and Comparisons counters tick up. (1) Drag n to its largest value, jump to Last, and divide total Operations by the Step count — that ratio is the amortized (average) cost per step, and it stays modest as $n$ grows. (2) Load the Special case preset to inject a few unusually costly moments, run to the end, and watch the per-step average barely move. (3) Walk forward one step at a time with Prev/Next: some steps are cheap and a rare one does extra work — those expensive steps are exactly what amortization smooths away.
§3 — Algorithm Analysis & Derivation
Symbol
Meaning
n
Input size
T(n)
Time complexity function
W(n)
Worst-case complexity
A(n)
Average / amortized complexity
Φ(S)
Potential function of data structure state S
α(n)
Inverse Ackermann function (~constant)
Step 1 — Why Amortized Analysis? Some operations are occasionally expensive but rarely so. Worst-case per operation is too pessimistic. Amortized analysis averages cost over a sequence — giving tighter (lower) bounds. Example: dynamic array resize costs O(n) but happens every n inserts.
Step 2 — Aggregate Method. Compute total cost T(n) of n operations, divide by n. Example: binary counter (increment n times). Bit i flips at most n/2^i times. Total flips: ∑_{i=0}^{log n} n/2^i < 2n. Amortized cost per increment: 2n/n = O(1).
Step 3 — Accounting Method. Assign amortized cost â to each operation (may differ from actual cost). Extra = credit stored on data structure. Must ensure: ∑â_i ≥ ∑c_i (never go into debt). Dynamic array: assign amortized cost 3 per insert. 1 for current insert, 1 saved on new element, 1 saved on element in first half. When resize: 2 credits per element pay for copy. Total: amortized O(1).
Step 4 — Potential Method. Φ(D) maps each data structure state to a real number. Amortized cost of op i: â_i = c_i + Φ(D_i) − Φ(D_{i-1}). Total amortized = total actual + Φ(D_n) − Φ(D_0). If Φ(D_n) ≥ Φ(D_0): amortized is upper bound on actual. Choose Φ wisely.
Step 5 — Dynamic Array Example. Φ(D) = 2·size − capacity. After insert without resize: ΔΦ = +2. Amortized = 1 + 2 = 3. After resize (capacity doubles, size+1): ΔΦ = 2(size+1) − 2·capacity − (2·size − capacity) = 2 − capacity = 2 − size ≈ −size (at a resize the array is full, so capacity = size). Amortized = (size+1) − size = O(1).
Step 6 — Splay Tree Potential. Splay tree: Φ(T) = ∑_{x} log(size(x)) = sum of log-subtree-sizes. Each splay operation (zig, zig-zig, zig-zag) has amortized cost O(log n). Self-adjusting: recently accessed nodes move to root — frequently accessed nodes stay near top. Actual worst case: O(n) per operation, but amortized O(log n).
§4 — Frequently Asked Questions
What is the difference between worst-case and amortized analysis? concept+
Worst-case: cost of the single most expensive operation. Amortized: average cost per operation over a sequence. A dynamic array insert is O(n) worst case (during resize) but O(1) amortized over n inserts. Using worst-case gives O(n²) for n inserts — too pessimistic.
When should you use potential method vs accounting method? concept+
Potential method: better when a natural 'energy' function exists for the data structure state. Accounting method: better when individual operations have intuitive 'credits'. Both give identical results when done correctly. Potential method is more systematic for complex structures.
How does splay tree achieve O(log n) amortized? complex+
Splay tree rotates (splays) the accessed node to root. This is expensive for deep nodes but makes subsequent accesses faster. Potential Φ = ∑ log(size(x)). A splay on a deep node reduces potential significantly — paying the cost. A splay on a shallow node costs little. The two cases balance to O(log n) amortized.
Where is amortized analysis used in real systems? applied+
Java ArrayList / C++ std::vector: O(1) amortized push_back. Java HashMap: O(1) amortized insert with rehashing. Splay trees in Linux kernel (vm_area structures in some versions). Union-Find with path compression: O(α(n)) amortized. Multi-level page tables: O(1) amortized access.
Can amortized analysis give wrong per-operation bounds? nonobv+
Amortized bounds apply only over a SEQUENCE of operations starting from an empty structure. If you need worst-case PER operation (real-time systems, interactive apps), amortized is insufficient. A dynamic array resize takes O(n) in the worst case — unacceptable for real-time robotics. Use a different structure (e.g., a purely functional deque with O(1) worst case) instead.
What is the connection between potential method and physics? deep+
The potential function Φ is analogous to potential energy in physics. Stored potential energy pays for later kinetic work. In CS: cheap operations store 'credit' (increase Φ); expensive operations spend it (decrease Φ). The total work is bounded by initial + final potential plus amortized costs — exactly like conservation of energy.
§5 — Misconceptions & Implementation Errors
Conceptual Misconceptions
✗ Amortized O(1) means every operation takes O(1).
✓ Amortized O(1) means the AVERAGE over a sequence is O(1). Individual operations can be O(n). Example: dynamic array resize is O(n) but amortized O(1) per insert over n inserts.
✗ Amortized analysis requires the potential function to be zero initially.
✓ Must have Φ(D_0) ≤ Φ(D_n) so that ∑amortized ≥ ∑actual. Common choice: Φ(D_0) = 0 and Φ(D) ≥ 0 always. Not strictly required to start at 0.
✗ Worst-case amortized and worst-case are the same thing.
✓ Worst-case per operation and amortized are different. A stack with multipop has O(n) worst-case multipop but O(1) amortized per operation over n operations (since you can only pop what you pushed).
Implementation Errors
✗ Using potential Φ that can become negative.
✓ If Φ can go negative, amortized costs may underestimate actual costs. Always choose Φ ≥ Φ(D_0) (or Φ ≥ 0 if D_0 is empty) to ensure total amortized ≥ total actual.
✗ Applying amortized analysis to a single operation in isolation.
✓ Amortized cost is only meaningful over a SEQUENCE of operations from a specific initial state. Saying 'this single operation costs O(1) amortized' is meaningless without the context of a sequence.
✗ Doubling by 1.5x vs 2x doesn't affect amortized complexity.
✓ Any constant growth factor c > 1 gives O(1) amortized insert. But the constant differs: factor 2: amortized 3 per insert; factor 1.5: amortized ~5 per insert. Trade-off: larger factor = fewer resizes (time) but more wasted memory (space).