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

Subproblems given a value, against the length of the strings

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
Subproblems given a value, against the length of the stringsFull table at a measured slope of 1.98; Rolling frontier at a measured slope of 1.98. The strings are unrelated, over an alphabet of 4. On these axes a slope of 2 is a rectangle filled and a slope of 1 is a line.10010³10⁴10⁵length of each stringsubproblems given a valueFull table · 1.98Rolling frontier · 1.98one unit = one subproblem given a valuesubproblems given a value, n from 32 to 512

Subproblems given a value, against the length of the strings

Full table at a measured slope of 1.98; Rolling frontier at a measured slope of 1.98. The strings are unrelated, over an alphabet of 4. On these axes a slope of 2 is a rectangle filled and a slope of 1 is a line.

Drawn at 700 × 430, wide on the page. Everything above is what subproblem-count returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

23 essays call subproblem-count. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

—bcab—abca6388328188632571322513518753111111one unit = one invocation of the recurrence481 calls, 25 distinct subproblems When the algorithm is a table

The cost is the number of subproblems

 —sitting—kitten012345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455one unit = one subproblem given a value56 cells, filled in row order When the algorithm is a table

The same table, filled two ways

 —abrocadabro—abracadabra012101221012210122112222123321233212332123321233212322one unit = one subproblem given a value54 of 144 cells, 90 skipped When the algorithm is a table

A band as wide as the answer

 01234567891011120123456789101112123456789101112123456789101112345678910123456789123456781234567123456123451234123121one unit = one subproblem given a value91 cells, 364 transitions, 4.0 per cell When the algorithm is a table

The cells are not the cost

 —execution—intention87777776569888888765one unit = one subproblem given a value100 cells computed, 20 held at once The other axis

The table nobody has to keep

 01234567891011120123456789101112122332223333122222332231222222223122222233122222221222222122222122221222122121one unit = one subproblem given a value91 cells, 156 transitions, 1.7 per cell When the algorithm is a table

The argmin that cannot go backwards

 —execution—intention0136101521283645247111622293746555812172330384756649131824313948576572141925324049586673792026334150596774808527344251606875818690354352616976828791944453627077838892959754637178848993969899one unit = one subproblem given a value100 cells, filled in diagonal order When the algorithm is a table

The order that has a depth

 —gactacgat—gattacagt0123456789101234567821012345673211123456432212345554332123456543321234765443222387655432339876554333one unit = one subproblem given a value100 cells, 100 held at once The data that is not a number

A distance that is a path through a grid

 —execution—intention0123456789112345667822234567773333455678434345667854444567776555555678766666656787777776569888888765one unit = one subproblem given a value110 cells for one divide step, 30 held The other axis

The alignment that fits in one line

 —gactacgat—gattacagt112223334244352461647one unit = one subproblem given a value21 matching pairs, 21% of the rectangle When the algorithm is a table

The cells that were never worth having

 —sitting—kitten111111101111110-1111110-1-111110-1-1-11110-1-1-10110-1-1-10-11one unit = one subproblem given a value-1, 0, 1 — 3 values, 2 bits each What the machine does

A column computed in machine words

 SETHno algorithm for k-SAT beats exhaustive search for every korthogonal vectorsno N^(2-e) algorithmedit distanceno n^(2-e) algorithmperformed heresplit and list, checked on 55,754 formulasquoted, not performed herequoted, not performed heresolid: an implication performed here · dashed: one that is quoteda conditional floor The floors

A floor that holds if something else does

 10³10⁴capacity Wsubproblems given a valueBottom-up table · 1.00Top-down, reachable only · 0.14one unit = one subproblem given a valuesubproblems given a value, W from 200 to 3200 What is taught wrongly

A table wider than its input

 10³10⁴10⁵words in the vocabularysubproblems given a valueevery table in full · 1.16best so far · 0.99answer known · 0.96one unit = one subproblem given a valuesubproblems given a value, n from 250 to 2424 When the algorithm is a table

The bound the search finds for itself

 10³10⁴10⁵words in the vocabularysubproblems given a valueevery table in full · 1.16a trie, no bound · 0.99best so far · 0.99a trie, best so far · 0.82one unit = one subproblem given a valuesubproblems given a value, n from 250 to 2424 When the algorithm is a table

The columns the candidates share

 1101001,000queries seenshare of the trie's prefixes ever visited10%20%30%50%70%100%misspelt vocabulary wordsmisspelt words it lacks7,709 prefixes, 2,424 wordsthe bounded walk, bound discovered When the algorithm is a table

A trie fitted to its queries

 01020share of queries for words the vocabulary lacksthousands of cells a query0%10%20%30%discover the boundone try at the medianone try at twoone, then two, then discovertold the distanceevery attempt chargeddotted: told the answer's distance When the algorithm is a table

A second try before any feature

 010203040the cap on an answer's distance, in editsthousands of cells a query123456nonewords it lacksa fifth unfamiliarmisspelt vocabulary wordsevery attempt charged2,000 + 600 queries When the algorithm is a table

A checker that stops at two edits

 00.1000.2000.30000.2500.5000.7501misspelt vocabulary words correctedunfamiliar words given a false suggestionat 1at 2at 3at 4cap aloneeach point: one threshold, with the cap of twoup and right: the cap alone When the algorithm is a table

The triples a typo writes

 00.1000.2000.3000.40000.2500.5000.7501misspelt vocabulary words correctedunfamiliar words given a false suggestionuniformdrawn by use0.50.5each point: one threshold; the right-hand end is the cap alonea tenth per edit When the algorithm is a table

The counts only short words carry

 whole listthree commonestcommonestone, counts unread0%50%100%3–4 letters83%64%5–6 letters95%83%7–8 letters99%95%9–10 letters99%99%11+ letters100%97%streams drawn by use; misspellings of vocabulary wordsties shared by expectation When the algorithm is a table

The commonest word at the distance

 0.7000.80011.251.501.752words shown, mean over answered queriesshare of misspellings correctedonetwothreer 10fixed listsratio rule, three in doubtratio rule, two in doubtone word or three, mixed3–4 letters, drawn by useexpected credit, ties shared When the algorithm is a table

A list as long as the doubt

 6570758011.251.501.752words shown a querycorrected, % of words of 3–4 lettersone wordtwo wordsthreeshare ruleratio rulecoin's lineε = 0.01up and left is better When the algorithm is a table

A second word judged by its own share

The library, page 5 of 5 — where subproblem-count sits