Welcome back.
We have discussed the recursive approach for solving the zero one knapsack problem.
Let's now quickly discuss the time and space complexity of the approach that we discussed.
So for every item, as we have seen, we have at the most two choices, which is to either include it
in the knapsack or excluded from the knapsack.
So if there are n items, the time complexity becomes two into two into two n times, which is two to
the power n.
So that's why the time complexity is of the order of two to the power n.
Remember over here, let's say this is item one.
And this is item two.
And let's say we just have two items.
So for the first item I have two choices which is include or exclude this item.
And for the second item I have two choices which is to include or exclude this item.
So that's why the total number of choices I have is two into two.
And when we expand this for n items, it becomes two into two into two, etc. n times, which is two
to the power n.
So that's why the time complexity is of the order of two to the power n, and the space complexity of
this solution is going to be of the order of n, because it's a recursive solution.
And we will be using space on the recursive call stack.
If you take a look at the recursion tree that we drew, you will notice that the maximum depth of the
tree is of the order of n.
So that's why the space complexity is of the order of n.