Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Parameter — where it appears

A number a structure's behaviour depends on that is chosen rather than derived — a block length, a sampling rate, a depth cap. Every one has a distribution behind it, and the distribution is usually cheaper to measure than the parameter is to sweep.

Named by 4 essays across 2 fields — each of them below, with the objects they name alongside it.

depth 0190.1%depth 19642.9%depth 24,92915.0%depth 37,00921.4%depth 48,47325.9%depth 56,24119.0%depth 63,31010.1%depth 71,2503.8%depth 84221.3%depth 91240.4%depth 10270.1%positions32,768 characters · 1172 phrasesmean 3.98

The number that would choose a cap

A depth histogram is one linear pass — 3.16 operations a character over thirty-two thousand of them — and it says the whole text sits at a mean depth of 3.98 with a worst of ten. Nobody prints it, and every choice of cap in this collection was made without it.

practice · Parse 0102030255075100125one sampled position in every …of both halves saved, per cent"about a sixth"the marks alone: 14.0%8,192 characters16.7% at one in 32

A sixth of what, exactly

The saving from a counting-only reverse half is 30.5% at one sampled position in four and 14.0% at one in a hundred and twenty-eight. A number quoted without its sampling rate is a number about a setting somebody chose.

wrong · Distance both halves, one in 3215.0 steps100.0% the sizeforward sampled one in 3215.0 steps83.3% the sizeforward sampled one in 167.0 steps88.4% the sizeforward sampled one in 83.0 steps98.5% the sizeforward sampled one in 41.7 steps118.8% the size8,192 characters · 6 occurrences5.0x faster, 98.5% the size

The saving, spent

A bidirectional index whose reverse half cannot locate is a sixth smaller. Give that sixth back to the half that does locate, and the same total size answers a locate five times faster.

practice · Distance 1.0%10.0%0.11fraction of characters changedper characterthe real runsthe real phrasesgenerated runsgenerated phrasesten revisions of one file · 24,580 characters2.32% against 3.24%

The dial that has no setting

The generator has one parameter. The real version history's run count asks it for 2.3% and its phrase count asks for 3.2% — and the reason is not that the dial is badly calibrated. Real edits average 7.3 characters a block and generated ones average 1.04.

wrong · Document

Named alongside it

The objects these essays reach for when they reach for this one.

PracticeBidirectional indexFM-indexIndex sizeLocateMeasurementRankRepetitionSamplingSpaceTradeBit vector

All concepts