1
00:00:00,480 --> 00:00:02,430
Hey there and welcome back.

2
00:00:02,430 --> 00:00:08,970
So we have discussed the approach that can be taken to implement the bottom up or tabulation approach

3
00:00:08,970 --> 00:00:11,100
for solving the LCS question.

4
00:00:11,100 --> 00:00:15,900
Let's now discuss the space and time complexity of this approach.

5
00:00:15,900 --> 00:00:18,690
Now the space complexity is obvious.

6
00:00:18,690 --> 00:00:26,940
It's going to be of the order of M into N, because we have this DP table over here and it has almost

7
00:00:26,940 --> 00:00:29,910
m columns and n rows.

8
00:00:29,910 --> 00:00:34,290
So the space complexity is of the order of m into n.

9
00:00:34,290 --> 00:00:36,900
Now what about the time complexity?

10
00:00:36,900 --> 00:00:44,790
The time complexity also is going to be of the order of m into n, because we need to iterate over all

11
00:00:44,790 --> 00:00:50,400
these cells till we find the value for this cell, which will give us the answer for the question.

12
00:00:50,400 --> 00:00:58,020
So the time complexity is also of the order of m into n, because notice over here we have m into n

13
00:00:58,020 --> 00:01:00,000
cells over here to fill.