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$
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$
  • $\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 '15 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$ – Yuval Filmus Jun 2 '15 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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