1
00:00:00,110 --> 00:00:01,010
Welcome back.

2
00:00:01,010 --> 00:00:07,340
So we have discussed how to solve the unbounded knapsack problem using the tabulation approach.

3
00:00:07,340 --> 00:00:10,040
Now this is the DP table that we used for it.

4
00:00:10,040 --> 00:00:14,450
And again remember what we did was we went through all of these cells.

5
00:00:14,450 --> 00:00:19,970
And then finally once we are done computing the value for this cell, we would return that because that

6
00:00:19,970 --> 00:00:21,110
gives us the answer.

7
00:00:21,110 --> 00:00:24,440
Now what would be the time complexity of this approach?

8
00:00:24,440 --> 00:00:32,510
The time complexity for this is going to be of the order of n into W, because we have N into W cells

9
00:00:32,510 --> 00:00:37,850
over here, and we would go through each of these cells to compute their value.

10
00:00:37,850 --> 00:00:43,340
And for computing the value for each cell we would just do constant time operations.

11
00:00:43,340 --> 00:00:43,730
Right.

12
00:00:43,730 --> 00:00:50,000
So that's why the total time complexity for coming up with the answer using this approach is going to

13
00:00:50,000 --> 00:00:52,550
be of the order of n into w.

14
00:00:52,550 --> 00:00:54,710
Now what about the space complexity?

15
00:00:54,710 --> 00:01:01,640
Again, the space complexity of this solution is also of the order of n into w, because we are using

16
00:01:01,640 --> 00:01:08,000
this DP table over here, which takes up space of the order of n into W, because we have n plus one

17
00:01:08,000 --> 00:01:10,400
rows and w plus one columns.

18
00:01:10,400 --> 00:01:16,880
Now you can optimize this and you can get a space complexity which is of the order of W.

19
00:01:16,880 --> 00:01:20,720
And for that you just need to follow the same approach that we discussed.

20
00:01:20,720 --> 00:01:26,390
When we discuss the zero one knapsack problem to come up with the space optimized tabulation approach.

21
00:01:26,390 --> 00:01:30,080
So go ahead and give it a try and try to do that on your own.