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

Every essay — page 16

Page 16 of 16, continuing through the fields in the same order.

What a bound is Counting The floors What the machine does Structures Two parameters The other axis When the algorithm flips a coin What the libraries do When it does not fit One pass, and no room The data that is not a number When the algorithm is a table The index that replaces the text What is taught wrongly Ladders Objects Search

What is taught wrongly

The comparisons that are made without units, the averages quoted without their distributions, and the bounds treated as predictions of speed.

1010³10⁴10⁵10⁶characters of textstepsbacktrackingThompson's NFAopen points: capped at4,000,000(a|a)*b12,158x at 20 characters

The folklore is about a matcher

Four million steps against three hundred and twenty-nine, on a twenty-character expression matched against twenty characters. One of the two machines doubles with every character of the input and the other does not, and only one of them is what a regular expression is.

8 figures