Tag
amortized-analysis
- Sep 22, 2026 Leftist and Skew Heaps: Merging in Logarithmic Time How a rank stored per node bounds the right spine, why skew heaps drop the rank and still amortise to logarithmic merge, and what the recursion costs. data structures
- Sep 9, 2026 Fibonacci Heaps and the Amortised Case for Decrease-Key How deferred consolidation makes meld and decrease-key constant amortised, what the potential function measures, and why the theoretical win rarely survives contact with memory. data structures
- Jun 26, 2026 Bottom-Up Heap Construction in Linear Time Why sifting down from the middle of the array builds a heap in O(n) rather than O(n log n), and how the node-counting argument bounds the total work. data structures
- May 28, 2026 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. algorithms
- Apr 9, 2026 Incremental Rehashing: Spreading a Resize Across Operations How two tables and a migration cursor turn an O(n) resize pause into constant work per operation, and what lookups must do while both tables are live. data structures
- Jan 21, 2026 The Prefix Function and Linear-Time Exact Matching How the prefix function records the longest proper border of each pattern prefix, and why following failure links keeps total matching work linear in the text length. algorithms
- Dec 2, 2025 Union by Rank and Path Compression: Two Heuristics That Fix the Chain How attaching the smaller tree under the larger bounds forest height, how rewriting parent links during a find flattens future traversals, and why the two heuristics must be analysed together. data structures
- Oct 9, 2025 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. algorithms
- Aug 31, 2025 Cuckoo Hashing and the Guarantee of Two Probes How two hash functions and a displacement rule give worst-case constant lookup, why insertion can cycle, and how a stash or a larger bucket count makes it succeed. data structures
- Mar 20, 2025 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. algorithms
- Aug 19, 2024 Splaying: Amortized Restructuring Without Stored Balance How a splay step moves an accessed node to the root, why zig-zig pairing matters, and how a potential function yields O(log n) amortized access with zero metadata. data structures
- Jun 3, 2024 The Inverse Ackermann Bound and Why It Is Effectively Constant How the α(n) function is defined, why the amortized cost of a disjoint-set sequence lands there, and what the matching lower bound says about improving it. data structures
- Sep 30, 2023 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. algorithms
- Mar 31, 2023 Binomial Queues and the Carry Chain of Merges Why storing trees of size 2^k makes merge look like binary addition, how extract-min decomposes the forest, and what the lazy structure costs in pointers. data structures
- Nov 18, 2022 Pairing Heaps and the Two-Pass Merge How a self-adjusting heap replaces rank bookkeeping with a left-to-right then right-to-left merge, why melding is constant time, and what the amortised bounds actually are. data structures