Problem Detail: Dynamic programming algorithm for Knapsack is stated to have complexity $mathcal O (nW)$. However, I’ve also seen the complexity stated as $mathcal O (n^2V)$, where $V=max v_i$. (Here $n$ is the number of items and $W$ the weight limit). I see from the algorithm that the first complexity measure is correct: http://en.wikipedia.org/wiki/Knapsack_problem Can someone tell me, why the other complexity measure works ?
Asked By : Shuzheng
Answered By : Yuval Filmus
The first complexity measure is in terms of the target weight, the second in terms of the heaviest element. Since $W leq nV$ (or rather, we can assume that $W leq nV$), the first estimate $O(nW)$ implies the second $O(n^2V)$. So $O(nW)$ is a stronger estimate than $O(n^2V)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/43175
