1
00:00:00,140 --> 00:00:07,280
Let's now discuss the space and time complexity of the memoization approach for the zero one knapsack

2
00:00:07,280 --> 00:00:07,970
problem.

3
00:00:08,000 --> 00:00:10,940
The space complexity is evident.

4
00:00:10,940 --> 00:00:17,810
It's going to be of the order of N into W, because we have to create and store this 2D array.

5
00:00:17,810 --> 00:00:21,230
So this array over here has w columns.

6
00:00:21,230 --> 00:00:22,880
So the columns are over here.

7
00:00:22,880 --> 00:00:24,590
And then you have n rows.

8
00:00:24,590 --> 00:00:28,850
So that's why the space complexity is of the order of n into w.

9
00:00:28,850 --> 00:00:36,110
And the time complexity is also going to be of the order of n into W, because that's the maximum or

10
00:00:36,110 --> 00:00:41,240
the upper bound of the number of computations that we would have to do, because we're just doing every

11
00:00:41,240 --> 00:00:42,410
computation once.

12
00:00:42,410 --> 00:00:48,530
And the maximum possible subproblems that there can be is of the order of n into W.

13
00:00:48,530 --> 00:00:53,060
So the time complexity is also of the order of n into W.

14
00:00:53,090 --> 00:01:01,790
Now do remember the memoization approach is still a recursive approach and therefore in some rare cases

15
00:01:01,790 --> 00:01:08,480
where we are dealing with high values or large values, we still have the risk of encountering a stack

16
00:01:08,480 --> 00:01:09,500
overflow error.

17
00:01:09,500 --> 00:01:14,000
So that's where the tabulation approach becomes very handy.

18
00:01:14,000 --> 00:01:17,270
And let's discuss that in the next video.