Pseudo-Polynomial Time Complexity
# Pseudo-Polynomial Time Complexity
The runtime is some polynomial in the numeric value of the input, rather than in the number of bits required to represent it.
Knapsack Problem The DP time complexity is $O(nC)$ where C is the capacity of the bag and n is the number of items. Capacity C needs log(C) bits to represent. If x is the number of bits, $x = log(C), C = 2^x$.
This is exponential in the number of bits.