= Pseudo-polynomial time
{wiki}
An <algorithm> has <pseudo-polynomial time> when its running time is bounded by a <polynomial> in the numerical magnitudes of input quantities, rather than necessarily in their encoded length. The <dynamic programming> table for the <0-1 knapsack problem> uses $O(nW)$ arithmetic operations for $n$ items and capacity $W$. A <binary numeral system> encoding needs only $O(\log(W+1))$ bits for that capacity, so the table bound can be exponential in the number of capacity bits. This distinction does not claim that every input requires exponential work.
Back to article page
