1
00:00:00,630 --> 00:00:02,400
Hey there and welcome back.

2
00:00:02,640 --> 00:00:09,690
Let's now take a look at the space and time complexity of the bottom up or tabulation approach for solving

3
00:00:09,690 --> 00:00:11,550
the palindromic substrings question.

4
00:00:11,550 --> 00:00:15,270
So this is the DP table that we used for solving this question.

5
00:00:15,270 --> 00:00:22,200
Now because we needed this DP table, the space complexity of this solution is going to be of the order

6
00:00:22,200 --> 00:00:23,190
of n square.

7
00:00:23,610 --> 00:00:29,730
When it comes to the time complexity for this approach, it's also going to be of the order of n square,

8
00:00:29,730 --> 00:00:37,380
because we have operations over here for each substring, and the total number of substrings is n into

9
00:00:37,380 --> 00:00:38,550
n plus one by two.

10
00:00:38,550 --> 00:00:44,490
And for each substring over here we're going to do constant time operations, which involves things

11
00:00:44,490 --> 00:00:51,570
like checking whether I is equal to J or whether it's just a two character string, or for longer strings,

12
00:00:51,570 --> 00:00:56,490
whether DP at I plus one j minus one is true or not.

13
00:00:56,490 --> 00:00:56,790
Right.

14
00:00:56,790 --> 00:01:00,570
So these are some of the constant time operations that we would need to do.

15
00:01:00,570 --> 00:01:07,380
But then we need to do this n into n plus one by two times because we have these many valid substrings.

16
00:01:07,380 --> 00:01:13,020
Now if you expand this term over here, you will get an n square term, which is the dominating term.

17
00:01:13,020 --> 00:01:17,730
And that's why the time complexity of this approach is of the order of n square.