Concept

Pseudo polynomial — where it appears

Polynomial in the numeric value of an input number and therefore exponential in the length of that number, so one more digit doubles the work. One extra digit in the capacity doubles the work, so a method described as efficient can be unusable on an instance that fits on one line.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

The same table, filled two ways

Top-down and bottom-up compute identical cells and return identical answers. One of them asks the table half a million questions and recurses four hundred frames deep; the other asks none and recurses none — and on a knapsack it fills twenty-two times as many cells as anything can reach.

tables · Table

A table wider than its input

The knapsack table has (n+1)(W+1) cells and is called polynomial. Adding one character to the input doubles it — across four settings the table grows sixty-four times while the input it is written from grows by half.

wrong · Bound

Named alongside it

The objects these essays reach for when they reach for this one.

Cost model Dynamic programming Knapsack Measured count Memoisation Subproblem Approximation Auxiliary space Call stack Complexity class Edit distance Encoding

All concepts