O(n*W) looks like a polynomial time, but it is not, it is pseudo-polynomial.
Time complexity measures the time that an algorithm takes as a function of the length in bits of its input. The dynamic programming solution is indeed linear in the value of W, but exponential in the length of W — and that’s what matters!
More precisely, the time complexity of the dynamic solution for the knapsack problem is basically given by a nested loop:
// here goes other stuff we don't care about
for (i = 1 to n)
for (j = 0 to W)
// here goes other stuff
Thus, the time complexity is clearly O(n*W).
What does it mean to increase linearly the size of the input of the algorithm? It means using progressively longer item arrays (so n, n+1, n+2, …) and progressively longer W (so, if W is x bits long, after one step we use x+1 bits, then x+2 bits, …). But the value of W grows exponentially with x, thus the algorithm is not really polynomial, it’s exponential (but it looks like it is polynomial, hence the name: “pseudo-polynomial”).
Further References
- http://www.cs.ship.edu/~tbriggs/dynamic/index.html
- http://websrv.cs.umt.edu/classes/cs531/index.php/Complexity_of_dynamic_programming_algorithm_for_the_0-1_knapsack_problem_3/27