Hey there and welcome back!
In the previous videos, we have discussed the approach that we can take to solve the palindrome partitioning
question.
Let's now discuss the space and time complexity of the approach that we came up with.
So when it comes to the space complexity, notice that it's going to be of the order of n square, because
we have to build this DP table.
And this takes space of the order of n square.
Also remember the backtracking part that we discussed will take up space on the recursive call stack.
But notice over here the maximum depth of this is just going to be of the order of n.
And because n is less than n square, we can say that the space complexity of this solution is of the
order of n square.
Now what about the time complexity?
The time complexity of this solution is of the order of two to the power n into n.
Now let's try to understand this.
Now what are the things that take up computation, or which are the things in the solution that we came
up with in which the algorithm does work?
So there is the backtracking part, and there is the part where we build the DP array over here.
We have previously seen that building the 2d dp array has a time complexity of the order of n square.
So we have previously already discussed this.
So I'm not going to repeat it over here.
Now let's take a look at the backtracking part.
For this let's have the recursion tree that we previously discussed placed over here.
And the input string was aa ba.
Now first let's try to identify the number of ways in which a BA can be partitioned.
Now again we are trying to find the upper bound or the worst case scenario.
Now to think about the number of ways in which a BA can be partitioned.
Imagine that there are three roads kept at these places.
So I have one road over here, one road over here, and one road over here.
Now, to identify the different ways in which I can partition this string, I just need to identify
the number of ways in which I can pick three roads among these three roads.
The number of ways in which I can pick two roads among these three roads.
The number of ways in which I can pick just one road among these three roads, and the number of ways
in which I can pick zero roads among these three roads.
And once we have found these values, we just need to add these ways of partitioning the input string.
Now again, let me try to explain this a little bit further.
So if we were to pick three roads from the three roads available over here, that would be equivalent
to partitioning A, A, B, a in this manner because we have all the three roads.
So that gives us a, a, B, a.
But if I just pick two roads, then one way of picking two roads would be I just pick the first two
roads.
So this gives me the partition A, A and BA.
Now if I pick two roads in this manner then this gives me the partition a, a b a.
So notice that these are separate right.
So that's why if we can just identify the different ways in which we can pick 3 or 2 or 1 or 0 roads
from these three roads, it would give us all the ways of partitioning the string which is given to
us.
So let's now go ahead and write down the different ways in which we can do this.
So if I want to pick three roads out of the three roads, I can do that only in one way.
So if I do that, the partition that I get is a, a, B, a.
If I go ahead and just pick two roads, I could pick these two, I could pick these two, or I could
pick these two.
So that gives me three ways of partitioning the input string.
So that's a a b a a a b a and a a b a.
So these are the three ways in which I can partition the input string by just picking two roads out
of these three roads.
Now if I can just pick one road I can pick just this one or this one or this one.
So that gives me again three ways of partitioning the input string.
And the three ways are a, a, b a a a b a and a a b a.
And finally, if I can just pick zero roads then it gives me the partition a a b a.
So these are all the possible partitions which can be executed on the input string.
So this is one way.
This is three ways.
Over here we have three ways.
And over here we have one way.
Now how do we get these numbers.
It's not always convenient to go ahead and write it.
Out and check it.
So over here what we're doing is selecting three things.
Three rods out of three rods which is 3C3.
And over here I'm just selecting two rods out of these three rods.
And I can do this in three.
See two ways.
And over here I'm selecting one rod out of these three rods which can be done in three.
See one way.
And over here I'm selecting zero rods out of these three rods which can be done in three.
See zero ways okay.
So I have three.
See three over here.
Three.
See two over here three.
See one over here and three see zero over here.
Now I just need to add these up so it goes from three.
See zero up to three see three.
And in a previous video we have discussed the meaning of NCR.
So let's go ahead and add these up.
So we get 3C0 plus 3C1 plus 3C2 plus 3C3.
And in this case we had four characters in the input string.
So notice that this three is actually n minus one, where n is the length of the input string.
So it goes from n minus one zero up to n minus 1CN minus one.
Now this series over here is a famous series in maths.
So if we have NC0 plus NC1 etcetera up to n c n.
And that's what we have over here instead of n we just have n minus one.
So this over here sums up to two to the power n.
And because over here we have n minus one instead of n.
This series over here sums up to two to the power n minus one.
So what is this?
Two to the power n minus one.
This actually is the maximum or the upper bound of the number of partitions that we can do.
If we are given a string of length n again notice how did we find this?
We found the various ways of partitioning the input string by taking three out of these three rods,
two out of these three rods, one out of these three rods and zero out of these three rods.
So this gave us all the various possible ways of partitioning the input string, which is nothing but
n minus one, c zero, n minus one, c one, etc. up to n minus one, c n minus one.
And when we add these up we get two to the power n minus one.
So the maximum number of partitions that we can do is of the order of two to the power n, because this
is two to the power n minus one.
Now let's come back to the part where we were discussing the time complexity.
We said that the time complexity is equal to the time complexity required for the backtracking part,
plus the time complexity for building the DP table over here.
And this part was of the order of N square.
And we have already previously discussed this.
So we are not repeating it over here.
And we were left with finding the time complexity for the backtracking part.
Now we know that there are two to the power n minus one partitions.
And again, each partition in fact represents one of the leaf nodes in this recursion tree over here.
And for each partition we have to build the substrings which is an O of n operation.
Now you can think of it in this manner.
Notice that the maximum depth of this tree is of the order of n.
So through these n steps we are building the partition.
And we have to do this in the worst case for all partitions.
So building the substrings is an O of n operation.
And because we have two to the power n minus one partitions, the time complexity or the worst case
time complexity for the backtracking part is going to be of the order of n into two to the power n.
Now again, two to the power n minus one is written as two to the power n, because we just want to
know what's the order of the time complexity.
So that's why the time complexity of the backtracking part is of the order of n into two to the power
n, and over here the part where we build the DP has a time complexity of the order of n square.
Now between these two n into two to the power n is greater than n square.
That's why we can say that the time complexity of this approach is of the order of n into two to the
power n again, why is n into two to the power n greater than n square?
I can rewrite n square as n into n, so I have n over here and n over here.
And if I were to compare two to the power n and n two to the power n is greater than n.
That's why n into two to the power n is greater than n square.
And hence the time complexity of this solution is of the order of n into two to the power n.