1
$\begingroup$

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 ?

$\endgroup$

1 Answer 1

2
$\begingroup$

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)$.

$\endgroup$
2
  • $\begingroup$ Thank you, excellent answer. Now, the approximation algorithm (with $v_i$ scaled) runs in polynomial size in the input encoded as binary (not a pseudo polynomial), because the size $n$ and the size of the input is polynomially related ? $\endgroup$
    – Shuzheng
    Jun 2, 2015 at 13:59
  • $\begingroup$ I have no idea what "the approximation algorithm" is, but I'm sure you can answer your question yourself and don't need my help. $\endgroup$ Jun 2, 2015 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.