The other axis
Measuring what an algorithm keeps
The alloc and enter primitives, why a call stack is auxiliary space that no array counter reaches, and why peak and total have to be tracked separately rather than summarised as one number called "space".
The stack nobody counts
Recursion depth as auxiliary space — why total calls and peak depth are different numbers, the three space profiles of one traversal, and the two-line change that bounds quicksort's stack on every input.
The frontier between time and space
The Pareto set over comparisons and peak auxiliary space, what being dominated means that being slower does not, and how completely the frontier is rearranged by changing the input.
The space the model does not see
The limits of counting auxiliary space in slots — bytes, allocator overhead, the excluded input, the interaction with cache — and why the time–space product bound was attempted and cut rather than quoted.
The table nobody has to keep
Why the number of cells a dynamic program computes and the number it holds at once are independent resources, what a rolling frontier costs, and the answer it can no longer give.
The alignment that fits in one line
Hirschberg's divide and conquer for linear-space alignment, why the extra work is exactly twice and not approximately, and what the general time-for-space exchange looks like.
The clock that cannot see the burst
Why a clock's resolution is a floor on the burstiness a system can observe, what a timestamp costs as the resolution is refined, and why the resolution is almost never a decision anybody made.
What a window costs in bits
State against window length for the exponential histogram, the crossover with keeping the window outright, and where the bits actually go.
The text that does not have to be kept
Extraction and location from a self-index — why reproducing the text is what makes the size claim mean anything, and the sampling rate that trades bits against the work of turning a row into a position.
What a second pass buys
Peak state against passes for exact selection — the interval that narrows, the exponent fitted to the sweep, and why a split rule that needs no data is a bet on the distribution.
What is still proportional to n
The term a run-length index does not remove — why the sampling is proportional to the length, what fraction of the structure it becomes, and what changing it costs.
The cheap tail and the expensive merge
How the choice of error function decides both the size of a quantile summary and the exponent its merged size grows by, and why the two effects point the same way.
The tuples a summary does not report
Why a quantile summary's peak is its resident size plus its compression period, what that ratio is across ε, and why the number the structure reports is the wrong one to size an allocation from.
Every occurrence at the same price
Why the size-against-locate trade a sampling rate buys is a curve, and what it means that a structure sized by the run count is not on it.
The character that costs a chain
Why an index built on a parse produces a character by following copies, how deep those chains get, and what bounds them — which is nothing.
The structure paid for before the first query
What a range structure costs in bits before any query is asked, where the o(z log z) actually goes, and how much of the grid the index was already paying for.
The term that came back
What happens to a structure sized by a measure of repetition when the constraint that makes it readable is tightened all the way, and what the collapse says about the measure.
A bound that has to be paid for
What a lower-bound pruning costs in space, why the second index cannot be avoided, and how a saving in one currency is paid for in another.
One separator, or one for each
What each way of separating documents costs an index, why the cost is invisible until the alphabet crosses a power of two, and which structures require the expensive one.
Two bits a value, and what undoes them
What a succinct range minimum actually costs, in the parts the published bound is a sum of, and why the term that decides it is the map from an index to its parenthesis.
The structure that was supposed to halve
What a bidirectional index actually costs, why the second transform cannot be avoided, and what a structure named as a space fix turned out to be a fix for instead.
A bit for every bit
What a wavelet tree over a permutation costs, where its entropy is, and why a structure whose levels are balanced by construction has almost nothing for a compressor to take.
An index that cannot locate
A counting-only FM-index built, stripped and measured, with the parts it keeps, the parts it drops, and what a bidirectional index costs when one half is that.
What the chain cost
The size of the previous-occurrence chain measured against every other part of a document index, and what the apparatus costs once it is gone.
Two currencies for one separator
The three document joins priced in packed bits and in runs of the transform, and why the two answers diverge as a collection is cut more finely.
The array that says where is twice the samples
Where an FM-index's locating apparatus actually is, why the marks do not shrink when the sampling thins, and the floor every curve in the strand flattens onto.
The apparatus, three times smaller again
The document-listing apparatus priced at three stages, what each removal was worth, and where the remaining bits are.
The ladder, and the rung that spends
Three size changes to a bidirectional index applied cumulatively, and a fourth step that converts all of them into speed at almost no net size.
Half an index is three permutations
Where a Lempel–Ziv index's bits actually are, the permutation that is derivable from its neighbour, and a time-for-space choice never priced here.