Expert · Module 22
Amortized and probabilistic analysis
Reason about average costs over sequences of operations and over random choices.
Some of the most important guarantees in this track are not worst-case bounds on a single operation. Dynamic arrays, union-find and two-stack queues are fast over any sequence of operations; quicksort and hash tables are fast in expectation over their own random choices. This module makes those guarantees precise: aggregate, accounting and potential arguments for amortized costs, Las Vegas and Monte Carlo algorithms with fair shuffling and sampling, and universal hashing, which turns a hash table's average case into a promise that holds for every input.
- 1Amortized analysisPro — members onlySome operations are usually cheap and occasionally expensive. Amortized analysis bounds the total cost of any sequence of them, so the average per operation is guaranteed, even though a single operation may be slow.14 min
- 2Accounting and potential methodsPro — members onlyThe accounting method overcharges cheap operations and saves the surplus as credit for expensive ones. The potential method does the same with a single function of the structure's state. Both prove amortized bounds when simply adding up costs is hard.15 min
- 3Randomized algorithmsPro — members onlyRandomized algorithms flip coins to escape bad inputs, sample fairly, or answer quickly with a small chance of error. Analyzing them means computing expected costs and error probabilities that hold for every input.15 min
- 4Expected cost of hashingPro — members onlyHash tables are O(1) only in expectation, and only if the hash function spreads keys well. Choosing the function at random from a universal family makes that expectation hold for every set of keys, which is also the defense against hash-flooding attacks.15 min