retagged by
316 views

1 Answer

0 votes
0 votes
Depending on the implementation it can be O(nw) or O(2^n)

 To compute in O(2^n) is simple to implement: suppose there are n items in 0/1 knapsack you have 2 option for each item,either select it or reject it,so it becomes o(2^n).

Related questions

1 votes
1 votes
1 answer
1
gatecse asked Dec 9, 2020
654 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 respecti...
0 votes
0 votes
1 answer
2
Rohit Pandey asked Jun 27, 2018
769 views
What will be the time complexity if fractional knapsack is implemented using min heap instead of sorted arraya) O(nlogn)b)O(n^2)c)O(n)d) none of these