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
$\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$
  • $\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 May 13 '13 at 2:46
  • $\begingroup$ If you do it this way, the complexity is $O(n^2v_{\max})$. $\endgroup$ – Yuval Filmus May 13 '13 at 4:21

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.