Hey there and welcome back!
Previously we have discussed the recursive approach and we have also discussed the pseudocode for the
recursive approach.
Now let's go ahead and draw the recursion tree and then discuss the complexity analysis for the approach
that we have come up with.
So let's get started with drawing the recursion tree.
So for this let's take an example where the two strings are a, b, c and a c.
When we start with the algorithm, we will notice that these two characters are equal or they are the
same.
Therefore, we would call the recursive function for the remaining parts over here.
So the answer would be one plus the answer to the subproblem which is b, c, and c.
Now after this, when we are comparing these two characters, we see that they are not equal.
So we have to find the maximum between two calls.
So in one call we would keep this index over here itself and increment this index to the next place.
So the call becomes b c and nothing because over here there's nothing after c.
And if one of these is empty then we have seen that we would hit the base case and it would just return
zero.
Now, the other call over here would be keeping this over here as it is and incrementing this index
to this place over here.
So the call becomes C and C.
And over here, because these two are equal the answer becomes one plus.
And then we increment both these two nothing and nothing.
And when you don't have anything over here this would just return zero.
Therefore the answer for this sub problem becomes zero plus one which is one.
And that's what is returned over here.
And then between 0 and 1 the maximum is one.
So this subproblem over here will return one.
And then the answer is one plus what we get over here.
So the answer becomes one plus one which is equal to two.
So this is the recursion tree for the recursive approach that we have just now discussed for solving
the LCS problem.
Now let's try to think of what the maximum depth would be, so that we can use that to identify the
space complexity of the approach that we have discussed.
So let's say we have a, b, c and p q as the two strings which are given to us.
So initially we would be calling the recursive function with the indices zero and zero.
So let's write that over here.
And when we do this call we'll see that these two indices are not the same.
They are not equal.
Therefore we would have to do two calls and we would just increment one index in each call.
And that means we will call zero one and one zero.
Now zero one means we keep this index over here itself and we increment it over here.
So this string remains as it is.
And this string becomes just Q.
That's this call over here zero one.
And then we are comparing these two characters.
And we see that they are again not equal.
So we'll have to do two calls and we'll just increment one index at a time.
So one call for solving this becomes zero two where we increment this index and the other call becomes
one one where we only increment this index.
Now this call over here will return zero because notice that the last valid index in the second string
is one.
And we have already got two over here, which is beyond one now.
So this will not go down further.
And then over here we have one comma one where we are dealing with these two substrings.
Again, we see that these two are not equal.
So we'll have to do two calls one comma two and two comma one.
Again, one comma two would return zero because the last valid index over here is one.
But we have two over here.
But for finding two comma one the strings that we are considering are C and q, we again see that these
two are not equal.
And because of that we have to do two calls.
So the two calls that we have to do are two comma two and three comma one.
Now two comma two again will return zero because this index becomes two which is greater than this one.
And over here three comma one also will return zero because we have three over here which is greater
than the last valid index which is two.
Now let's go ahead and complete this branch as well.
So the strings that we are considering over here are b, c and p q because we have one comma zero and
because b and p are not equal, we will again have to do two calls where we increment only one index
at a time.
So the two calls are one comma one and two comma zero and one comma one.
Is this part where we are considering b, c and q.
Notice that again b and q are not equal.
So we'll have to do two calls which is one comma two and two comma one and one comma two will return
zero because two is greater than the last valid index over here, which is one and two comma one.
Again, when we're dealing with two comma one, we are dealing with c and q.
Now these two are not equal.
So we will have to do two calls two comma two and three comma one.
And these two will again return zero because this is beyond one.
And this three over here is beyond this two.
Now let's go ahead and complete this branch over here.
Now to find two comma zero.
The substrings that we are considering are c and p q.
Again we see that c and p are not equal.
Now because of that we have to do two calls where we will be incrementing one index at a time.
So we get two comma one and three comma zero.
Now three comma zero will return zero because three is beyond two, which is the last valid index over
here.
And to find two comma one again we're dealing with c and q.
And these characters are not equal.
So we will have to do two calls two comma two and three comma one.
And these two will return zero.
Now our intention for drawing this was to identify the maximum depth in the recursion tree, because
that would help us identify the recursive call stack space that we are using.
So notice over here that the maximum depth is equal to 512345.
And over here the lengths were two and three.
And this five over here is actually two plus three right.
So this is three.
The length over here is three.
And over here the length is two.
And that's why the maximum depth is five.
Because we are only changing one index at a time.
So over here notice we we kept going down down down till we reached over here.
Because over here this index is out of scope and therefore it will return zero.
Notice that in none of the previous calls over here did we hit the base case.
So we have to go down till over here.
And this is the maximum depth.
Now there are branches with lesser depth.
But the maximum depth helps us identify the upper bound of the space complexity or the space used on
the recursive call stack.
And therefore the space complexity of this solution is of the order of n plus m.
Now what about the time complexity?
The time complexity of this solution is going to be of the order of two to the power n plus m, which
can be thought of as two into two, into two, etc. n plus m times.
Think of the Fibonacci question that we have done and the time complexity that we are getting over here.
And the way that we get this is very much similar to how we identified the time complexity of the recursive
solution for the Fibonacci question.
Now, again, you can think of it as every level has two x nodes as the previous level, and there are
at max n plus m levels.
So the maximum or the upper bound of the time complexity is two to the power n plus m, or the maximum
number of nodes that can be there in this recursive tree is two to the power n plus m, and in each
node we are just doing constant amount of work.
So that's why the time complexity is of the order of two to the power n plus m into one.
Or we can just say of the order of two to the power n plus m.