Amortized Analysis: Complete Beginner's Guide For students.

Amortized analysis averages a few expensive operations over a long sequence of cheap ones. Instead of bounding one operation's worst case, it bounds the average cost over the worst possible sequence.

Many data structures occasionally do costly maintenance, like resizing an array, yet feel fast in practice. It proves the average cost stays low, explaining why dynamic arrays and hash tables perform well despite occasional expensive steps.

Key Concepts

• Amortized cost: the guaranteed average cost per operation over a sequence, even though individual operations may cost much more or less.
• Aggregate method: bound the worst-case total T(n) of n operations, then divide: amortized cost = T(n)/n.
• Accounting method: assign each operation a price; cheap ops overpay into a bank, expensive ones spend it, keeping the balance nonnegative.
• Potential method: define a potential Phi of the structure's state; amortized_i = actual_i + Phi_after − Phi_before, so stored potential pays for future expensive steps.
• Dynamic array: an array doubling in capacity when full, giving O(1) amortized appends.

Formulas

• Aggregate method: worst-case total T(n) for n operations gives amortized cost T(n)/n per operation.
• Accounting method: amortized = actual + deposited credit; total credit must never go negative over any prefix.
• Potential method: amortized_i = actual_i + Phi_i − Phi_{i-1}; telescoping shows total amortized cost bounds total actual cost.
• Doubling array bound: n appends cost at most n + (1 + 2 + 4 + … + n/2) = 2n - 1, so amortized cost is below 2, which is O(1).

Worked Example

Append 8 elements to an array starting at capacity 1, doubling when full. Each plain append costs 1: base cost 8. Resizes at sizes 1, 2, 4 copy 1, 2 and 4 elements: total resize cost 7. Total cost: 8 + 7 = 15. Amortized cost: 15/8 = 1.875, a constant. Though the 5th append alone cost 5, the average is under 2: appending is O(1) amortized.

Common Misconceptions

• Amortized analysis is the same as average-case analysis. Average-case averages over random inputs; amortized analysis averages over an operation sequence in the worst case, with no randomness.
• O(1) amortized means every operation is fast. A single operation can still cost O(n); the guarantee covers only the average over many operations.
• Amortized bounds apply to one unlucky input. They apply to sequences: one expensive operation is paid for by many cheap ones before it.

Real-World Applications

• Dynamic arrays: Python lists, Java ArrayLists and C++ vectors use doubling for O(1) amortized append.
• Hash tables: resizing as the load factor grows keeps insertions O(1) amortized.
• Splay trees and union-find: self-adjusting structures powering caches and Kruskal's algorithm.
• Incremental algorithms: garbage collectors batch expensive work over cheap steps.

Amortized analysis matches real behavior: mostly cheap, occasionally expensive, cheap on average. For rare maintenance work, use the aggregate, accounting or potential method to prove the average stays constant.