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