3
$\begingroup$

I have this confusion related to the time complexity of the algorithm solving the knapsack problem using dynamic programming

enter image description here

I didn't get how the time complexity of the algorithm came out to be $O(nV^*)$

$\endgroup$

1 Answer 1

1
$\begingroup$

Since computing each cell in the table is $O(1)$, the running time is just the size of the table. The first coordinate ranges from $1$ to $n$, and the second one from $0$ to the maximal value ever encountered (so it's really a dynamic table), which is $V^*$.

$\endgroup$
2
  • $\begingroup$ I have a confusion. We run the dynamic programming with two loops lets say i from 1 to n and another loop v from 0 to nvmax. As mentioned in the picture, they have $V* <= nv_{max}$. So the limit is already decided isn't it? $\endgroup$
    – user34790
    Commented May 13, 2013 at 2:46
  • $\begingroup$ If you do it this way, the complexity is $O(n^2v_{\max})$. $\endgroup$ Commented May 13, 2013 at 4:21

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.