Skip to content
— g a c t a c g a t — g a t t a c a g t 0 1 2 3 4 5 6 7 8 9 1 0 1 2 3 4 5 6 7 8 2 1 0 1 2 3 4 5 6 7 3 2 1 1 1 2 3 4 5 6 4 3 2 2 1 2 3 4 5 5 5 4 3 3 2 1 2 3 4 5 6 5 4 3 3 2 1 2 3 4 7 6 5 4 4 3 2 2 2 3 8 7 6 5 5 4 3 2 3 3 9 8 7 6 5 5 4 3 3 3 one unit = one subproblem given a value 100 cells, 100 held at once
Distance
1
A distance that is a path through a grid
2
A band as wide as the answer
3
The alignment that fits in one line
4
The row that starts at zero
5
The filter that feeds the table
+ 28 more
33 essays · text
block transfers In order, 0 to n−1 1,024 1.0× a scan · 64.0 elements per transfer Every B-th element (B = 64) 65,536 64.0× a scan · 1.0 elements per transfer Uniformly at random 61,407 60.0× a scan · 1.1 elements per transfer a scan of this array is 1,024 transfers B = 64, M = 4,096 (M/B = 64) 64× between the cheapest order and the dearest
Transfer
1
One access, eight kilobytes
2
A tree with nodes the size of a block
3
Sorting what will not fit
4
The layout that is told nothing
5
The writes nobody counted
+ 27 more
32 essays · applied
after 0 writes 0 cmp after 32 writes 32 cmp after 64 writes 63 cmp after 95 writes 94 cmp after 127 writes 125 cmp after 159 writes 157 cmp random input, seed stated in lib/count.js 157 comparisons in this run
Count
1
Counting instead of timing
2
Fitting a class to measurements
3
One run, four counts, four answers
4
The count somebody chose
5
Counting the coin flips
+ 26 more
31 essays · counting
100 10³ 10³ 10⁴ 10⁵ 10⁶ 10⁷ V counted work Breadth-first Dijkstra, binary heap Dijkstra, all V queued Bellman–Ford, all passes V from 64 to 2048, sparse, fixed average degree work = scans + visits + relaxations + queue comparisons
Graph
1
Counting on a graph
2
Two parameters, one bound, no order
2
The constant that is practically constant
3
The queue decides the class, and the pseudocode does not name it
3
A list and a block of memory
+ 24 more
29 essays · graphs
level 1 level 2 level 3 level 4 level 5 key 21 search: 8 comparisons, 3 hops 26 keys, p = 0.5, seed 20260810 57 coin flips decided the shape
Randomness
1
A structure made of coin flips
2
The height is a distribution, and the coin is a parameter
2
One pass, k slots, and two randomness budgets
3
A filter that is allowed to be wrong
3
A hash is a family, not a function
+ 23 more
28 essays · randomness
0 4 8 16 24 32 characters every key shares operations 0 72,581 145,162 Character comparisons Radix sort, characters read Element comparisons one unit = one character comparison element comparisons constant at 3,955
Symbol
1
The comparison that is not one comparison
2
The shift the pattern already knows
3
The text that answers without reading it
4
A match decided by a number
5
The index that is the text
+ 22 more
27 essays · text
suffix array + text 311,296 19.00 b/ch counter array per symbol 5,407,710 330.06 b/ch FM-index, plain 100,947 6.16 b/ch FM-index, compressed 36,804 2.25 b/ch the packed text one bar shaded darker needs the text · English-like sigma 21, sample 64
Index
1
An index larger than what it indexes
2
A search that runs backwards
3
The index that is smaller than the text
4
Rank is the only thing it does
5
The text that does not have to be kept
+ 19 more
24 essays · indexes
i s · h o l d s · n o · t h e · t h e · o f · o f · r a t h e r · c o u n t · c l a s s · t h a t · i s · a l g o r i t h m · o 1 1 1 1 1 1 1 2 1 1 1 1 1 1 5 1 1 4 1 1 3 1 1 1 1 1 1 1 2 1 1 1 2 2 2 1 3 1 1 1 1 1 1 2 1 2 phrase lengths below each block · a shaded block is a literal English-like · 64 characters z = 46 · 17 literals
Parse
1
The phrases a text copies from itself
2
An index with z in its size
3
The occurrences that cross a boundary
4
The character that costs a chain
5
The measure that cannot see the alphabet
+ 18 more
23 essays · text
10⁵ 10⁶ 10³ 10⁴ 10⁵ comparisons cache misses (modelled) Insertion sort Selection sort Bubble sort Merge sort Heapsort Quicksort, first Quicksort, median-3 Quicksort, random Shellsort Merge + cutoff fully associative · 64 lines × 8 elements · LRU a modelled count, not a time
Machine
1
The count is not the time
2
The cliff where the data stops fitting
2
Where an algorithm looks
3
Where insertion sort actually wins
4
The branch the machine guesses
+ 17 more
22 essays · machine
4 6 8 12 windows window length spanning a join in no document with a separator English-like · 8 documents 44 invented at m = 12
Document
1
The occurrences a join invents
2
One separator, or one for each
3
A list of documents is not a list of occurrences
4
The cost that is the size of the answer
5
A corpus that was not generated
+ 15 more
20 essays · wrong
— b c a b — a b c a 63 88 32 8 1 88 63 25 7 1 32 25 13 5 1 8 7 5 3 1 1 1 1 1 1 one unit = one invocation of the recurrence 481 calls, 25 distinct subproblems
Table
1
The cost is the number of subproblems
2
The same table, filled two ways
3
The table nobody has to keep
4
The cells are not the cost
5
The argmin that cannot go backwards
+ 12 more
17 essays · tables
a c g t a c g t seen -> 0 3 1 3 3 0 3 1 1 3 0 3 3 1 3 0 a gap of k characters costs 2k rows: expected · columns: seen · unit: bits linear gaps
Cost
1
A cost that is not one
2
A cell that has to know where it is
3
A distance that is not a distance
4
The zero that moves the answer out of the corner
5
A distance divided by a length is not a rate
+ 9 more
14 essays · tables
peak slots held at once, logarithmic 1 8 64 512 4096 Insertion sort 1 1 Selection sort 1 1 Bubble sort 1 1 Heapsort 1 1 Shellsort 1 1 Quicksort, median of three 22 log n Quicksort, random pivot 28 log n Quicksort, first-element 29 log n Merge sort with a cutoff 4,106 n Merge sort 4,110 n n = 4,096, random input one slot = one array element or one stack frame
Space
1
Measuring what an algorithm keeps
2
The stack nobody counts
2
In place is a claim, and it is usually wrong about quicksort
3
The frontier between time and space
3
The space the model does not see
+ 9 more
14 essays · space
every algorithm that makes at most 4 comparisons the 24 orderings of 4 elements root 16 leaves 16 seated · 8 with no leaf one comparison per level, two outcomes per comparison ⌈log₂(4!)⌉ = 5 comparisons
Floor
1
The floor under every comparison sort
2
How close anything gets to the floor
3
The floor moves when the question does
3
The adversary who hides the edge
3
The floor when the values repeat
+ 8 more
13 essays · floors
3,600 — the window opens 4,000 — now 32 16 16 16 8 8 4 the window edge 215 in buckets −16 for the oldest = 200 true 200 0.3% out sliding-window model · ε = 0.2, k = 5 · 1,764 merges 406 bits against 400
Window
1
The summary that has to forget
2
The floor under a window
3
What a window costs in bits
4
The bits that say when
5
A register that became a list
+ 8 more
13 essays · streaming
bits per symbol huffman 3.937 1.01× the floor arithmetic (adaptive) 3.898 1.00× the floor LZSS (window 4096) 2.113 0.54× the floor LZ78 3.147 0.81× the floor H₀ = 3.892 16,384 symbols · alphabet 21 · floor shown is H0 = 3.892 bits/symbol model: order 0 · Words from a fixed vocabulary best here: 2.113 bits/symbol
Bits
1
The bits a coder emits
2
The optimal code that is beaten
3
The model is the compressor
4
The dictionary that builds itself
5
The transform that emits nothing
+ 7 more
12 essays · floors
one summary, k = 32 769 one summary, k = 256 0 8 summaries of 32, merged 536 worst error over the top keys, in arrivals concentration 1.00 — the mean share of a heavy key held by one shard 8 shards · hashed · balanced merge 536 against matched 0
Merge
1
The state a merge is standing in for
2
The partition the analysis did not mention
3
The order nobody fixed
4
The floor a histogram already knows
5
The bill a partition only divides
+ 7 more
12 essays · streaming
Timsort 95,770 ships Introsort 130,863 ships pdqsort 114,408 ships Dual-pivot 116,836 ships Merge sort 96,145 textbook Heapsort 187,796 textbook Quicksort, median-3 119,098 textbook algorithm comparisons random, n = 8,192 comparisons, counted exactly
Practice
1
The sort the library ships
2
A run is a property of the input
3
When galloping pays
4
The pattern that defeats the pattern
5
A guarantee that depends on an allocation
+ 6 more
11 essays · practice
above 0.01 of the stream · 13 really are one pass: 18 candidates two passes: 13 keys, exactly the heavy ones 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 128 counters · carry 1,376 bits 5 of 18 spurious
Pass
1
The pass that was never a parameter
2
What a second pass buys
3
A floor one pass cannot get under
4
The pass that runs the other way
5
What a pass costs when it is a file
+ 5 more
10 essays · bounds
100 10³ 100 10³ 10⁴ 10⁵ 10⁶ n comparisons Insertion Heapsort Merge Shellsort a power law is a straight line here comparisons, counted exactly
Bound
1
What O-notation does not say
2
The constant the notation drops
3
A limit is not a prediction
4
The depth limit that almost never fires
5
A table wider than its input
+ 4 more
9 essays · bounds
All essays