General Topic Doubt: Algorithms - Dynamic Programming

Question

Read the following statements about 0/1 Knapsack problem.

(i) Time complexity of Knapsack is O(n* W) where W is the weight of the Knapsack and there are n items.
(ii) Time complexity of Knapsack is min( O(n*W) , O(2^n) ) where W is the weight of the Knapsack and there are n items.
(iii) Knapsack can be implemented in O(n*W) space .
(iv) Knapsack can be implemented in O(W) space.

where n is the number of items and W is the weight of the Knapsack .

Mark the correct option

1.   (i) and (iii) is true
2.   (ii) and (iii) is true
3.   (i) ( iii) (iv) is true
4.  (ii) (iii) (iv) is true.

Comments

Option 2.  is the correct answer.

Statement 2 says, time complexity of knapsack is O(n*W) since we need to compare each element weight to 0-W.

but sometimes W will be far bigger hence 2^n exahustive search will be better.

Statement 3 is also correct.