educative.io

Why space complexity is O(2^n) in Basic Solution?

Courses
,
#1

I knew that in 1/2 knapsack problem, the basic solution space complexity is O(n) because we have n stacks at most. What about unbounded knapsack problem? How to analyze the number of the stack?

Does anyone have some ideas?

Thank you!

#2

My understanding is as following:

  1. Imagine a recursion tree.
  2. In every layer of the recursion tree, every tree node has two children. One represents includes the num[i] this time, the other one represents not includes the num[i] this time.
  3. The hight of the recursion tree is C(capacity) + N(number of items), because we can choose the same smallest item multiple times (until by choosing one more time we reach the capacity, (C/min(num)) - 1, which is asymptotically equivalent C), and then not choose the rest items (N - 1)
  4. The total number of nodes in the recursion tree is then 2**(C + N)

Please correct me if I am wrong.