1
00:00:00,500 --> 00:00:07,130
Previously, we have discussed the tabulation or bottom up approach for solving palindrome partitioning

2
00:00:07,160 --> 00:00:10,190
two by just using a one dimensional array.

3
00:00:10,220 --> 00:00:16,340
Now let's go ahead and take a look at the space and time complexity of the approach that we have discussed.

4
00:00:16,340 --> 00:00:23,270
So the time complexity for this part, which is to build a 2D array called is palindrome will be of

5
00:00:23,270 --> 00:00:24,740
the order of n square.

6
00:00:25,480 --> 00:00:29,950
And we have discussed this multiple times previously, so we're not going to repeat it over here.

7
00:00:29,980 --> 00:00:33,310
Now let's take a look at this part of the pseudocode.

8
00:00:33,340 --> 00:00:37,540
Now this part over here will almost do n iterations.

9
00:00:37,540 --> 00:00:42,160
And this part over here will also do n iterations in the worst case.

10
00:00:42,160 --> 00:00:48,130
So these two together will have a time complexity of the order of n into n.

11
00:00:48,250 --> 00:00:55,210
And then the operations over here are just constant time operations, because checking whether the string

12
00:00:55,210 --> 00:01:00,100
that goes from start to end is a palindrome is going to be a constant time operation, because we're

13
00:01:00,100 --> 00:01:05,050
just going to use this DP table over here, which is something that we've already pre-computed.

14
00:01:05,050 --> 00:01:08,890
And then we just have to identify the minimum between a set of values.

15
00:01:08,890 --> 00:01:15,310
So that's why the total time complexity of this approach is going to be of the order of N square.

16
00:01:15,700 --> 00:01:17,770
Now what about the space complexity?

17
00:01:17,770 --> 00:01:24,280
The space complexity of this solution is also going to be of the order of n square, because we have

18
00:01:24,280 --> 00:01:30,160
to construct this 2D dp array for checking whether a substring is a palindrome or not.

19
00:01:30,190 --> 00:01:34,630
Now this part over here takes up space only of the order of n.

20
00:01:34,630 --> 00:01:40,090
Therefore, the total space complexity of the solution is going to be of the order of n square.