 Pseudo-polynomial time

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 lengths. 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 representation needs only $O(\log (W+1))$ bits for that capacity, so the table bound can be exponential in the number of capacity bits. For example, capacities below $2^b$ fit in $b$ bits, while a table with one entry for every capacity can have nearly $2^b$ columns. The numerical-value bound does not claim that every instance requires exponential work.

Pseudo-polynomial time refers to a classification of algorithmic complexity that is related to the performance of algorithms specifically in the context of certain types of integer-based problems. An algorithm is said to run in pseudo-polynomial time if its running time is polynomial in the numeric value of the input, rather than the size of the input in terms of the number of bits it takes to represent that input.