Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?
Polynomial time means that the running time is bounded by a polynomial in the length of the input.  The running time here is bounded by&nbsp;$nW$.  $n$, the number of items, is surely less than the length of the input, so that part is fine. But $W$, the target weight, is a number that appears in the input, in binary. In $\ell$&nbsp;bits, you can write a number up to $2^\ell$ so $W$&nbsp;is potentially exponential in the length of the input, not polynomial.