1 1 vote how is 0/1 knapsack time complexity O(2^n/2) ? Algorithms knapsack-problem time-complexity + – A_i_$_h 655 views answer comment Share Follow Print See 1 comment 1 1 comment reply bhuv commented Jul 26, 2017 reply Follow flag I think that was O(2^n) for bigger W, otherwise it would be O(nW). 0 0 replyShare Please log in or register to add a comment.
0 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). Red_devil answered Sep 16, 2017 Red_devil comment Share Follow See 1 comment 1 1 comment reply A_i_$_h commented Sep 16, 2017 reply Follow flag yes O(2^n) is okay what is O(2^n/2) ? 0 0 replyShare Please log in or register to add a comment.
