1
00:00:00,400 --> 00:00:02,380
Hey there and welcome back!

2
00:00:02,440 --> 00:00:09,970
In the previous videos, we have discussed the tabulation approach by just using a one dimensional array

3
00:00:09,970 --> 00:00:11,920
for solving the Liz question.

4
00:00:12,250 --> 00:00:17,860
Let's now take a look at the space and time complexity of the approach that we have come up with.

5
00:00:17,860 --> 00:00:20,500
So the space complexity is obvious.

6
00:00:20,500 --> 00:00:25,930
It's going to be of the order of N because we have to have this DP table.

7
00:00:25,930 --> 00:00:32,320
And again we are not using any recursive call stack space because the solution over here is an iterative

8
00:00:32,320 --> 00:00:32,650
one.

9
00:00:32,650 --> 00:00:36,340
So the space complexity is of the order of n.

10
00:00:36,340 --> 00:00:42,490
Now when it comes to the time complexity, it's still going to be of the order of n square.

11
00:00:43,090 --> 00:00:44,440
Now why is that the case?

12
00:00:44,440 --> 00:00:51,160
Remember initially when I was equal to one, we had to do one operation because j took the value zero.

13
00:00:51,160 --> 00:00:56,500
And then when I is equal to two, j will take the values zero and one.

14
00:00:56,500 --> 00:00:57,760
That's two operations.

15
00:00:57,760 --> 00:01:01,600
Then when I is equal to three, j will take these three values.

16
00:01:01,600 --> 00:01:03,010
So that's three operations.

17
00:01:03,010 --> 00:01:10,030
So the total number of operations that we would have to do will be one plus two plus three etc. up to

18
00:01:10,030 --> 00:01:14,950
n minus one which equals n minus one into n divided by two.

19
00:01:14,950 --> 00:01:20,500
Now this over here when you simplify it there will be an n square term.

20
00:01:20,500 --> 00:01:23,380
And that's why because that is the dominating term.

21
00:01:23,380 --> 00:01:27,700
The time complexity of this approach is of the order of n square.

22
00:01:28,060 --> 00:01:32,710
So these are the approaches that we have discussed for the Liz question.

23
00:01:32,710 --> 00:01:40,210
Now the bottom up 1D approach has a space complexity of the order of N and the time complexity of the

24
00:01:40,210 --> 00:01:41,530
order of N square.

25
00:01:41,530 --> 00:01:48,520
Now notice that the time complexity over here is much better than the time complexity that we had achieved

26
00:01:48,520 --> 00:01:55,510
with just recursion, and the space complexity over here is also of the order of N, which was the space

27
00:01:55,510 --> 00:01:57,940
complexity that we had used up over here.

28
00:01:57,940 --> 00:02:01,120
But again, we are not using recursive call stack space.

29
00:02:01,120 --> 00:02:05,410
So that's an added advantage as this solution is an iterative one.