1
00:00:00,430 --> 00:00:01,600
Welcome back.

2
00:00:01,630 --> 00:00:06,430
We have discussed the recursive approach for solving the zero one knapsack problem.

3
00:00:06,430 --> 00:00:12,220
Let's now quickly discuss the time and space complexity of the approach that we discussed.

4
00:00:12,220 --> 00:00:19,300
So for every item, as we have seen, we have at the most two choices, which is to either include it

5
00:00:19,300 --> 00:00:22,780
in the knapsack or excluded from the knapsack.

6
00:00:22,780 --> 00:00:30,880
So if there are n items, the time complexity becomes two into two into two n times, which is two to

7
00:00:30,880 --> 00:00:31,660
the power n.

8
00:00:31,660 --> 00:00:36,670
So that's why the time complexity is of the order of two to the power n.

9
00:00:36,670 --> 00:00:39,910
Remember over here, let's say this is item one.

10
00:00:40,540 --> 00:00:42,040
And this is item two.

11
00:00:42,040 --> 00:00:43,780
And let's say we just have two items.

12
00:00:43,780 --> 00:00:49,120
So for the first item I have two choices which is include or exclude this item.

13
00:00:49,120 --> 00:00:53,800
And for the second item I have two choices which is to include or exclude this item.

14
00:00:53,800 --> 00:00:58,510
So that's why the total number of choices I have is two into two.

15
00:00:58,510 --> 00:01:05,230
And when we expand this for n items, it becomes two into two into two, etc. n times, which is two

16
00:01:05,230 --> 00:01:06,100
to the power n.

17
00:01:06,100 --> 00:01:12,760
So that's why the time complexity is of the order of two to the power n, and the space complexity of

18
00:01:12,760 --> 00:01:17,620
this solution is going to be of the order of n, because it's a recursive solution.

19
00:01:17,620 --> 00:01:21,370
And we will be using space on the recursive call stack.

20
00:01:21,370 --> 00:01:27,100
If you take a look at the recursion tree that we drew, you will notice that the maximum depth of the

21
00:01:27,100 --> 00:01:28,900
tree is of the order of n.

22
00:01:28,900 --> 00:01:32,620
So that's why the space complexity is of the order of n.