1
00:00:00,200 --> 00:00:07,490
Let's now take a look at the space and time complexity of the space optimized tabulation approach.

2
00:00:07,520 --> 00:00:14,180
Now, as we have discussed, we are just going to store two 1D arrays of size w.

3
00:00:14,180 --> 00:00:18,050
So prev is going to be an array of size w.

4
00:00:18,050 --> 00:00:21,140
And cr is going to be an array of size w.

5
00:00:21,140 --> 00:00:28,010
So the space complexity is not of the order of n into W, as was the case previously.

6
00:00:28,010 --> 00:00:33,350
But now the space complexity is just going to be of the order of W.

7
00:00:33,350 --> 00:00:38,360
So notice that we have significantly improved the space complexity.

8
00:00:38,360 --> 00:00:45,110
Now when it comes to the time complexity, it's still going to be of the order of N into W, because

9
00:00:45,110 --> 00:00:48,500
we have to go through all of these cells and compute the values.

10
00:00:48,500 --> 00:00:55,430
So the time complexity is still O of n into W, but the space complexity is of the order of W.

11
00:00:55,430 --> 00:01:01,400
And these are the four approaches that we have discussed for solving the zero one knapsack problem.