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.

15 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

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