I have this confusion related to the time complexity of the algorithm solving the knapsack problem using dynamic programming
I didn't get how the time complexity of the algorithm came out to be $O(nV^*)$
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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^*$.
answered May 13, 2013 at 2:10
-
$\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$ May 13, 2013 at 2:46
-
$\begingroup$ If you do it this way, the complexity is $O(n^2v_{\max})$. $\endgroup$ May 13, 2013 at 4:21