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^*)$
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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^*$.