281 views

Which of the following is a correct time complexity to solve the $0/1$ knapsack problem where $n$ and $w$ represents the number of items and capacity of knapsack respectively?

1. $O(n)$
2. $O(w)$
3. $O(nw)$
4. $O(n+w)$

Time complexity of  0-1 Knapsack Problem using dynamic problem is $\mathcal{O(nw)}$

Option $C$ is correct.

1 vote