1
00:00:00,450 --> 00:00:01,470
Welcome back.

2
00:00:01,500 --> 00:00:07,500
Let's now take a look at the space and time complexity for the approach that we have just now discussed

3
00:00:07,500 --> 00:00:09,540
for solving palindrome partitioning two.

4
00:00:09,660 --> 00:00:16,350
Now, because we do need this DP table over here, the space complexity is going to be of the order

5
00:00:16,350 --> 00:00:17,310
of n square.

6
00:00:17,880 --> 00:00:22,470
When it comes to the time complexity, it's going to be of the order of n cube.

7
00:00:22,740 --> 00:00:24,210
Now why is that the case?

8
00:00:24,240 --> 00:00:31,230
So to get all the possible substrings, we will need to do work of the order of n square, because we

9
00:00:31,230 --> 00:00:38,250
know that for a string of length n, there can be substrings of the order of n square or n into n plus

10
00:00:38,250 --> 00:00:39,570
one by two substrings.

11
00:00:39,570 --> 00:00:41,160
So we already know this.

12
00:00:41,160 --> 00:00:47,790
So because there are substrings of the order of n square to get to all the substrings over here, we'll

13
00:00:47,790 --> 00:00:50,040
have to do work of the order of n square.

14
00:00:50,070 --> 00:00:56,850
Now for each of these ij combinations we'll have to do work of the order of n.

15
00:00:56,850 --> 00:01:03,360
In the worst case over here, where k takes the values from I up to j minus one.

16
00:01:03,360 --> 00:01:09,870
So that's why in the worst case scenario, the total time complexity is going to be of the order of

17
00:01:09,870 --> 00:01:13,200
n square into n, which is equal to n cube.

18
00:01:13,200 --> 00:01:17,370
So that's why the time complexity of this approach is of the order of n cube.

19
00:01:17,400 --> 00:01:21,150
In the next video let's think whether we can do better or not.

20
00:01:21,150 --> 00:01:24,990
And let's try to come up with an approach with a better time complexity.