Algorithms · Cluster
Complexity Analysis
Asymptotic bounds, recurrences, and amortized accounting.
- 01 Amortized Analysis of Dynamic Arrays Why appending to a growable array is O(1) on average despite occasional O(n) reallocations, and how the accounting argument is constructed.
- 02 Asymptotic Notation as Sets of Functions, Not Growth Rates Big-O names a set of functions fixed by a constant and a threshold. What those witnesses promise for two-input bounds, for logarithms, and for small n.
- 03 The Master Theorem and the Recursion Tree Behind Its Three Cases Divide-and-conquer recurrences are solved by comparing the work at the root with the work at the leaves. Where the three cases come from, and which recurrences slip past them.
- 04 Comparison Lower Bounds From Decision Trees and Adversaries Counting distinguishable outcomes gives the n log n sorting bound. When that counting is not available, an adversary argument supplies the same conclusion by a different route.
- 05 Expected Cost, Amortized Cost, and Where the Average Comes From Three kinds of average appear in algorithm analysis. They average over different things, hold under different adversary models, and cannot be substituted for one another.
- 06 Space Complexity Accounting for Recursion, Auxiliary Buffers and Output Stack depth, explicit work arrays and output storage are three separate memory costs, and the convention for counting them decides whether an algorithm is called O(1) space, O(log n) or O(n).
- 07 Unit-Cost RAM, Word RAM and Bit Complexity as Three Different Machines The same algorithm can be linear, logarithmic or quadratic depending on whether operations are charged per step, per word, or per bit, and the choice of model decides which bounds are comparable.
- 08 The Potential Function Behind the Inverse-Ackermann Union-Find Bound Disjoint-set forests with union by rank and path compression cost O(m alpha(n)) for m operations, and the proof is a ranked accounting over nodes rather than any single tree shape.
- 09 Stranded Credit: Why Amortized Bounds Fail Under Persistence and Laziness Credit earned by earlier operations is only spendable if the state carrying it survives, so persistent versions and deferred computation can strand potential, and the potential argument has to be redesigned rather than reapplied.
- 10 Smoothed Analysis: Why the Simplex Method Beats Its Worst Case Worst-case bounds are exponential and average-case bounds assume a distribution nobody can justify. Perturbing the input by a Gaussian turns the question into a function of how much noise the input carries.