Structures
What amortised means
What an amortised bound actually claims, why it is a statement about a sequence rather than an operation, the sawtooth of individual costs behind the constant, and where the distinction between amortised and worst case decides a design.
Choosing a growth factor
The growth factor of a dynamic array measured on both axes at once — amortised cost against wasted capacity — why no choice dominates, and what the memory allocator has to do with the factor 1.5 that several standard libraries use.
The order nobody fixed
Why merging counter summaries is not associative, how far apart the shapes of a merge tree drive the same answer, and what that costs a system that compares summaries rather than reading them.
The tree that is a list
What happens to an unbalanced binary search tree on sorted input, why the degeneration is total rather than partial, and what balancing actually buys measured against the ideal and against the disaster.
Building a heap from the bottom
Two ways to turn an array into a heap, measured across three orders of magnitude; why the n log n bound describes an input rather than an algorithm; and what the choice costs inside heapsort and inside a priority queue.
The priority nobody supplied
How a treap repairs the failure mode of a binary search tree without measuring anything, why the shape it produces is the shape a random insertion order would have given, and what the repair costs.
The probe nobody waits for
Robin Hood hashing measured against plain linear probing, where the mean is provably unchanged and the variance collapses — the clearest case here of a technique invisible to an average.
A bucket that becomes a tree
Java's treeify threshold measured under three hashes, why the Poisson argument says it never fires, and what it means to ship a mechanism whose entire value is in somebody else's mistake.
A tree with nodes the size of a block
The B-tree measured in block transfers against binary search over the same keys, why the fanout is a hardware parameter rather than a design taste, and why the measured cost is below the height.
The index that is the text
Building a suffix array by prefix doubling, why it makes no character comparisons at all, what Kasai's linear LCP array is doing, and where the break-even against simply scanning the text actually falls.
The items that survive k counters
The deterministic frequent-items structure, its shortfall bound, and a head-to-head against Count-Min at equal bits that comes out the other way from the way the field is usually described.
The summaries that add
Why register-wise maximum and cellwise addition lose nothing, what a counter table gives up when it merges, and why the distinction decides whether a distributed summary is reproducible.
Every substring, in fewer states than substrings
The suffix automaton, the two exact bounds on its size, the strings that attain them, and three unrelated routes to the same substring count.
A sketch that is allowed to be under
Count-Sketch against Count-Min at equal bits, why the error changes currency from the L1 norm to the L2 norm, and what is lost when an estimate stops being a bound.
The count that outlives its arrivals
Heavy hitters over a sliding window, and why a counter cannot be run backwards — the block decomposition, the slack it cannot remove, and the two errors that go opposite ways.
The counter that takes the smallest slot
A counter-based heavy-hitter structure that overestimates — the eviction rule, the error it records beside each count, why the bracket is empty exactly where the answers matter, and the reversal against Misra-Gries.
The bill a partition only divides
Why the merge damage of the two counter structures is one quantity split two ways, how the split is decided by the partition rather than the structure, and what the merge tree adds on top.
The shape that moves the bill
Why the order shards are combined in changes a quantile summary's size by forty per cent and its answers by less than the promise, and why the counter tables behave the other way round.
The fold that minimises the wrong thing
Why the size-ordered merge fold is provably optimal for the weighted path length and second-best for the damage, and which quantity actually tracks a fold's bill.
The shape one structure will not fold
Why a merge fold that saves a quantile summary a fifth of its space costs a counter table 2.7 times its error, and what a deployment holding both structures can do about it.
A rectangle over a permutation
How a wavelet tree over a permutation answers a rectangle query, what the descent and the lifting cost, and why the leaves have to exist even though they hold nothing.
The shape a range question is about
The Cartesian tree, why a range minimum is a question about a shape rather than about numbers, and the stack that builds it in one pass.
The runs a permutation does not leave
The run-coded bit vector the deferral asked for, why it costs more than the bits it replaces, and the shuffle control that says how much of the ordering was ever there.
One revision, one level
The worst and mean depth of the first k revisions of two real files, the offset a single document contributes, and the saturation that stops the chain deepening.
The tree the operation insists on
Optimal alphabetic codes computed by dynamic programming, measured against Huffman's tree and against a fixed-length code, on generated and real text.
A document already in the answer
The chainless document listing written out, the left-first order the equivalence depends on, and the two deliberate defects that must be caught.
The price of a boundary is what precedes it
Why cutting a text into documents costs runs in proportion to how predictably the documents end, measured against the run counts it explains.
The last array in the apparatus
What remains of a document-listing apparatus once the previous-occurrence chain and the range minimum have been removed, and why the last part is a different kind of object.
The branches that find nothing
A backtracking search's dead extensions counted, and what removing them rather than making them cheaper is worth.
A position split in two
The Elias–Fano construction applied to an index's sample marks, what each operation costs, and why the split is where it is.
Every copy points right
The ordering property a Lempel–Ziv parse guarantees, and the second time in this collection that a traversal order made a bookkeeping structure unnecessary.
Bits and steps on one frame
The convention that a change trading two currencies is drawn in both, applied to the one dial a self-index's locating apparatus depends on.
Two states per operator
The non-deterministic machine a regular expression compiles to, what its states are, and why the construction's linearity is structural rather than fortunate.