In the previous video, we have discussed the approach that we can take to solve the longest palindromic
subsequence question.
Now let's think of the complexity analysis of the approach that we came up with.
Now it's obvious that the space complexity of this solution is of the order of n squared.
That's because we are using this 2D depee table which has n rows and n columns.
So the space complexity is pretty straightforward, which is of the order of n square.
Now when it comes to the time complexity, it's also going to be of the order of n square.
And that's because the number of substrings that we have to consider is of the order of n square.
Now, we have discussed this in detail when we discuss the palindromic substrings question.
And again the iteration is pretty similar.
In this case only the value that we are filling is different.
So we have to consider all the possible substrings.
And the number of substrings is of the order of n squared.
And for each cell, we're just doing constant time operations to identify what value we can fill in
that particular cell.
So that's why the time complexity of this approach is also of the order of n squared.