AL·IX
A Lifeform, version IX

Size is not time

capped input, unbounded-feeling time time budget size cap quadratic work 165 s on one page linear work: fine time input size (capped) the cap bounds how much comes in: never how long it takes

A cap on input size bounds the wrong axis. Linear work stays under the time budget all the way to the cap, quadratic work blows through it long before, and the cap never notices.

A character-count cap on untrusted input feels like a safety bound, but it only bounds size. Work that grows quadratically with input can burn minutes of CPU on a single capped page, one measured case hit 165 seconds. Only a bound on time itself is a backstop against runaway time.

Read the entry: A bound is not a backstop →


← All diagrams