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

Series

A field says what an essay is about. A series follows one idea essay by essay — from the question that introduces it to the one that assumes all the others.
—gactacgat—gattacagt0123456789101234567821012345673211123456432212345554332123456543321234765443222387655432339876554333one unit = one subproblem given a value100 cells, 100 held at once

Distance

  1. 1 A distance that is a path through a grid
  2. 2 A band as wide as the answer
  3. 3 The alignment that fits in one line
  4. 4 The row that starts at zero
  5. 5 The filter that feeds the table
  6. +24 more
29 essays · text 048162432characters every key sharesoperations072,581145,162Character comparisonsRadix sort, characters readElement comparisonsone unit = one character comparisonelement comparisons constant at 3,955

Symbol

  1. 1 The comparison that is not one comparison
  2. 2 The shift the pattern already knows
  3. 3 The text that answers without reading it
  4. 4 A match decided by a number
  5. 5 The index that is the text
  6. +22 more
27 essays · text is·holds·no·the·the·of·of·rather·count·class·that·is·algorithm·o1111111211111151141131111111211122213111111212phrase lengths below each block · a shaded block is a literalEnglish-like · 64 charactersz = 46 · 17 literals

Parse

  1. 1 The phrases a text copies from itself
  2. 2 An index with z in its size
  3. 3 The occurrences that cross a boundary
  4. 4 The character that costs a chain
  5. 5 The measure that cannot see the alphabet
  6. +18 more
23 essays · text block transfersIn order, 0 to n−11,0241.0× a scan · 64.0 elements per transferEvery B-th element (B = 64)65,53664.0× a scan · 1.0 elements per transferUniformly at random61,40760.0× a scan · 1.1 elements per transfera scan of this array is 1,024 transfersB = 64, M = 4,096 (M/B = 64)64× between the cheapest order and the dearest

Transfer

  1. 1 One access, eight kilobytes
  2. 2 A tree with nodes the size of a block
  3. 3 Sorting what will not fit
  4. 4 The layout that is told nothing
  5. 5 The writes nobody counted
  6. +18 more
23 essays · applied 10010³10³10⁴10⁵10⁶10⁷Vcounted workBreadth-firstDijkstra, binary heapDijkstra, all V queuedBellman–Ford, all passesV from 64 to 2048, sparse, fixed average degreework = scans + visits + relaxations + queue comparisons

Graph

  1. 1 Counting on a graph
  2. 2 Two parameters, one bound, no order
  3. 2 The constant that is practically constant
  4. 3 The queue decides the class, and the pseudocode does not name it
  5. 3 A list and a block of memory
  6. +17 more
22 essays · graphs after 0 writes0 cmpafter 32 writes32 cmpafter 64 writes63 cmpafter 95 writes94 cmpafter 127 writes125 cmpafter 159 writes157 cmprandom input, seed stated in lib/count.js157 comparisons in this run

Count

  1. 1 Counting instead of timing
  2. 2 Fitting a class to measurements
  3. 3 One run, four counts, four answers
  4. 4 The count somebody chose
  5. 5 Counting the coin flips
  6. +16 more
21 essays · counting suffix array + text311,29619.00 b/chcounter array per symbol5,407,710330.06 b/chFM-index, plain100,9476.16 b/chFM-index, compressed36,8042.25 b/chthe packed textone bar shaded darker needs the text · English-likesigma 21, sample 64

Index

  1. 1 An index larger than what it indexes
  2. 2 A search that runs backwards
  3. 3 The index that is smaller than the text
  4. 4 Rank is the only thing it does
  5. 5 The text that does not have to be kept
  6. +16 more
21 essays · indexes 46812windowswindow lengthspanning a joinin no documentwith a separatorEnglish-like · 8 documents44 invented at m = 12

Document

  1. 1 The occurrences a join invents
  2. 2 One separator, or one for each
  3. 3 A list of documents is not a list of occurrences
  4. 4 The cost that is the size of the answer
  5. 5 A corpus that was not generated
  6. +15 more
20 essays · wrong level 1level 2level 3level 4level 5key 21search: 8 comparisons, 3 hops26 keys, p = 0.5, seed 2026081057 coin flips decided the shape

Randomness

  1. 1 A structure made of coin flips
  2. 2 The height is a distribution, and the coin is a parameter
  3. 2 One pass, k slots, and two randomness budgets
  4. 3 A filter that is allowed to be wrong
  5. 3 A hash is a family, not a function
  6. +14 more
19 essays · randomness 10⁵10⁶10³10⁴10⁵comparisonscache misses (modelled)Insertion sortSelection sortBubble sortMerge sortHeapsortQuicksort, firstQuicksort, median-3Quicksort, randomShellsortMerge + cutofffully associative · 64 lines × 8 elements · LRUa modelled count, not a time

Machine

  1. 1 The count is not the time
  2. 2 The cliff where the data stops fitting
  3. 2 Where an algorithm looks
  4. 3 Where insertion sort actually wins
  5. 4 The branch the machine guesses
  6. +9 more
14 essays · machine peak slots held at once, logarithmic18645124096Insertion sort11Selection sort11Bubble sort11Heapsort11Shellsort11Quicksort, median of three22log nQuicksort, random pivot28log nQuicksort, first-element29log nMerge sort with a cutoff4,106nMerge sort4,110nn = 4,096, random inputone slot = one array element or one stack frame

Space

  1. 1 Measuring what an algorithm keeps
  2. 2 The stack nobody counts
  3. 2 In place is a claim, and it is usually wrong about quicksort
  4. 3 The frontier between time and space
  5. 3 The space the model does not see
  6. +9 more
14 essays · space 3,600 — the window opens4,000 — now32161616884the window edge215 in buckets−16 for the oldest= 200true 2000.3% outsliding-window model · ε = 0.2, k = 5 · 1,764 merges406 bits against 400

Window

  1. 1 The summary that has to forget
  2. 2 The floor under a window
  3. 3 What a window costs in bits
  4. 4 The bits that say when
  5. 5 A register that became a list
  6. +8 more
13 essays · streaming one summary, k = 32769one summary, k = 25608 summaries of 32, merged536worst error over the top keys, in arrivalsconcentration 1.00 — the mean share of a heavy key held by one shard8 shards · hashed · balancedmerge 536 against matched 0

Merge

  1. 1 The state a merge is standing in for
  2. 2 The partition the analysis did not mention
  3. 3 The order nobody fixed
  4. 4 The floor a histogram already knows
  5. 5 The bill a partition only divides
  6. +7 more
12 essays · streaming —bcab—abca6388328188632571322513518753111111one unit = one invocation of the recurrence481 calls, 25 distinct subproblems

Table

  1. 1 The cost is the number of subproblems
  2. 2 The same table, filled two ways
  3. 3 The table nobody has to keep
  4. 4 The cells are not the cost
  5. 5 The argmin that cannot go backwards
  6. +7 more
12 essays · tables every algorithm that makes at most 4 comparisonsthe 24 orderings of 4 elementsroot16 leaves16 seated · 8 with no leafone comparison per level, two outcomes per comparison⌈log₂(4!)⌉ = 5 comparisons

Floor

  1. 1 The floor under every comparison sort
  2. 2 How close anything gets to the floor
  3. 3 The floor moves when the question does
  4. 3 The adversary who hides the edge
  5. 3 The floor when the values repeat
  6. +6 more
11 essays · floors acgtacgtseen ->0313303113033130a gap of k characters costs 2krows: expected · columns: seen · unit: bitslinear gaps

Cost

  1. 1 A cost that is not one
  2. 2 A cell that has to know where it is
  3. 3 A distance that is not a distance
  4. 4 The zero that moves the answer out of the corner
  5. 5 A distance divided by a length is not a rate
  6. +5 more
10 essays · tables answered 19.90%25%50%75%100%0.36420.52,170value, logarithmicfraction of the stream at or belowrank ±2%value 19.3–21.9answered 2.9% out20,000 values · log-normal, σ = 1.2 — a latency distribution · Greenwald–Khanna, ε = 0.02rank 1.02% · value 2.9%

Rank

  1. 1 The error that is on the rank
  2. 2 A promise about the rank is not a promise about the value
  3. 3 An error measured against the answer
  4. 4 The digest that promises nothing
  5. 5 The promise that does not survive the tree
  6. +4 more
9 essays · streaming 1,00010,0000.1bits of state heldrelative errorHyperLogLog (-0.49)LogLog (-0.44)bottom-k (-0.38)50,000 distinct keys · 14 runs per point · truth counted exactlybest: 2.00% at 10,240 bits

Sketch

  1. 1 The answer that is allowed to be wrong
  2. 2 Counting past what the register holds
  3. 3 The estimate that is a median of means
  4. 4 A count that is never under
  5. 5 The items that survive k counters
  6. +4 more
9 essays · streaming —1234152abcbcbccbsolid: a transition on a character · dashed: a suffix or failure link8 states ≤ 9, 9 transitions ≤ 11

Automaton

  1. 1 Every substring, in fewer states than substrings
  2. 2 One pass for every pattern at once
  3. 3 Two states per operator
  4. 4 The exponential is in the expression
  5. 5 What a character costs on four machines
  6. +3 more
8 essays · structures rank among the boundaries, sorted by the text before themsorted by the text after0 in the rectanglepattern "ss is un"split after 40 end with the left half0 begin with the rightEnglish-like · 2 copies of 512z = 156 · 0 crossing

Grid

  1. 1 The candidates a filter cannot avoid
  2. 2 A rectangle over a permutation
  3. 3 The operations a candidate count leaves out
  4. 4 The structure paid for before the first query
  5. 5 A bit for every bit
  6. +3 more
8 essays · indexes

All essays