1
00:00:00,730 --> 00:00:07,600
Let's now discuss the space and time complexity for the tabulation approach that we have just now discussed.

2
00:00:07,600 --> 00:00:12,760
So notice over here, the tabulation approach is iterative in nature.

3
00:00:12,760 --> 00:00:17,140
And we will not be using space on the recursive call stack.

4
00:00:17,140 --> 00:00:25,480
So the space complexity but still is of the order of n into w because we have this DP table.

5
00:00:25,480 --> 00:00:29,260
And you can see that it has n rows and w columns.

6
00:00:29,260 --> 00:00:33,340
So the space complexity is of the order of n into w.

7
00:00:33,340 --> 00:00:38,050
And the time complexity is also of the order of n into W.

8
00:00:38,050 --> 00:00:43,210
Because as you have seen, we are going row by row and filling each of the cells over here.

9
00:00:43,210 --> 00:00:49,870
So the space complexity and time complexity of this solution is of the order of n into W.