1
00:00:00,050 --> 00:00:05,540
In the previous video, we have discussed the approach that we can take to solve the longest palindromic

2
00:00:05,540 --> 00:00:06,860
subsequence question.

3
00:00:06,890 --> 00:00:12,170
Now let's think of the complexity analysis of the approach that we came up with.

4
00:00:12,200 --> 00:00:18,650
Now it's obvious that the space complexity of this solution is of the order of n squared.

5
00:00:18,680 --> 00:00:24,650
That's because we are using this 2D depee table which has n rows and n columns.

6
00:00:24,650 --> 00:00:29,390
So the space complexity is pretty straightforward, which is of the order of n square.

7
00:00:29,690 --> 00:00:34,910
Now when it comes to the time complexity, it's also going to be of the order of n square.

8
00:00:34,910 --> 00:00:40,880
And that's because the number of substrings that we have to consider is of the order of n square.

9
00:00:40,910 --> 00:00:46,250
Now, we have discussed this in detail when we discuss the palindromic substrings question.

10
00:00:46,250 --> 00:00:48,950
And again the iteration is pretty similar.

11
00:00:48,950 --> 00:00:52,040
In this case only the value that we are filling is different.

12
00:00:52,040 --> 00:00:55,670
So we have to consider all the possible substrings.

13
00:00:55,670 --> 00:00:59,060
And the number of substrings is of the order of n squared.

14
00:00:59,060 --> 00:01:05,240
And for each cell, we're just doing constant time operations to identify what value we can fill in

15
00:01:05,240 --> 00:01:06,260
that particular cell.

16
00:01:06,260 --> 00:01:11,870
So that's why the time complexity of this approach is also of the order of n squared.