Hey there and welcome back.
Let's now discuss the space and time complexity of the recursive approach that we have discussed for
solving the edit distance question.
Now for this.
First, let's quickly draw the recursion tree to identify the maximum depth of the recursion tree,
because that would help us identify the space and time complexity.
So over here, let's take an example.
Let's say the two words that are given to us are a, b, c, and pq.
And we need to convert ABC to PQ.
So initially we are going to compare the characters at index zero and zero respectively in ABC and PQ.
So we would make a function call and the inputs would be zero comma zero.
And we see that these two are not equal.
Therefore we would have to compute insert, delete and replace.
We have discussed previously that in the case of insert we would only move the second index, which
is one.
So this zero is zero itself and this zero has become one.
Now why is that the case.
Let's quickly review it.
So we have ABC and PQ.
And we see that these two are not equal.
And we are inserting P over here.
So this pointer stays over here.
And only this pointer has to be moved.
And then next we would want to compare these two characters.
So that's why we only move the second pointer in this case.
Now for delete again we have ABC and PQ.
We see these two are not equal.
And we delete this character.
Now we would have to move this pointer.
So that's why this zero becomes one.
And this stays over here itself.
So this zero is zero itself.
And then finally for replace we have ABC and PQ.
We see these two are not equal.
So this A is replaced and we have P over here.
Now these two are equal and therefore both pointers would have to be moved.
So zero zero becomes one comma one for replace.
Now let's continue and see how the recursion tree looks like.
So over here we have zero one.
So we are comparing this and this.
Again we see that these are not equal.
And we would need to do three calls insert delete and replace.
When we insert we only change the second pointer.
So over here this becomes zero comma two.
For deleting we only change the first pointer.
So this becomes one comma one.
And for replace we have to increment both the pointers.
So this becomes one comma two.
Now let's continue with this branch.
So over here we have one comma one.
Again we see that these are not equal.
So we would have to do three calls insert delete and replace.
And over here we have two comma one.
And again notice that we would have to do insert delete and replace.
And at this point we would start returning because this is out of bound.
This is the last valid character over here.
Over here also we have three which is greater than two.
And over here we have two which is greater than one.
So all of this would return and there would be no level further down.
So the maximum depth that you can see in this recursion tree is equal to five.
So that's 12345.
And this five over here is the sum of the lengths of these two strings over here which is three plus
two.
So the maximum depth of the recursion tree is three plus two which is equal to five.
And therefore the space complexity of this solution is going to be of the order of n plus m, where
n and m are the lengths of word one and word two, respectively.
So again, the space complexity is of the order of n plus m, because we will be using up space on the
recursive call stack.
Now what about the time complexity?
The time complexity is going to be of the order of three to the power n plus m, because in each level,
in the worst case, we have three times the number of nodes that are there in the previous level.
For example, over here we had one node.
Node is that in the next level we are having three nodes.
So in the worst case every subsequent level has three x the number of nodes as the previous level.
And that's why the time complexity is of the order of three to the power n plus m.
Notice that this is pretty much similar to the way that we discussed the time complexity for the Fibonacci
question, where we implemented a recursive solution.