Hey there and welcome back.
Let's now take a look at the space and time complexity of the bottom up or tabulation approach for solving
the palindromic substrings question.
So this is the DP table that we used for solving this question.
Now because we needed this DP table, the space complexity of this solution is going to be of the order
of n square.
When it comes to the time complexity for this approach, it's also going to be of the order of n square,
because we have operations over here for each substring, and the total number of substrings is n into
n plus one by two.
And for each substring over here we're going to do constant time operations, which involves things
like checking whether I is equal to J or whether it's just a two character string, or for longer strings,
whether DP at I plus one j minus one is true or not.
Right.
So these are some of the constant time operations that we would need to do.
But then we need to do this n into n plus one by two times because we have these many valid substrings.
Now if you expand this term over here, you will get an n square term, which is the dominating term.
And that's why the time complexity of this approach is of the order of n square.