Welcome back.
Let's now take a look at the space and time complexity for the approach that we have just now discussed
for solving palindrome partitioning two.
Now, because we do need this DP table over here, the space complexity is going to be of the order
of n square.
When it comes to the time complexity, it's going to be of the order of n cube.
Now why is that the case?
So to get all the possible substrings, we will need to do work of the order of n square, because we
know that for a string of length n, there can be substrings of the order of n square or n into n plus
one by two substrings.
So we already know this.
So because there are substrings of the order of n square to get to all the substrings over here, we'll
have to do work of the order of n square.
Now for each of these ij combinations we'll have to do work of the order of n.
In the worst case over here, where k takes the values from I up to j minus one.
So that's why in the worst case scenario, the total time complexity is going to be of the order of
n square into n, which is equal to n cube.
So that's why the time complexity of this approach is of the order of n cube.
In the next video let's think whether we can do better or not.
And let's try to come up with an approach with a better time complexity.