1
00:00:00,400 --> 00:00:02,290
Hey there and welcome back.

2
00:00:02,320 --> 00:00:08,680
Let's now discuss the space and time complexity of the recursive approach that we have discussed for

3
00:00:08,680 --> 00:00:10,600
solving the edit distance question.

4
00:00:10,630 --> 00:00:11,710
Now for this.

5
00:00:11,710 --> 00:00:18,850
First, let's quickly draw the recursion tree to identify the maximum depth of the recursion tree,

6
00:00:18,850 --> 00:00:22,480
because that would help us identify the space and time complexity.

7
00:00:22,480 --> 00:00:24,580
So over here, let's take an example.

8
00:00:24,580 --> 00:00:28,810
Let's say the two words that are given to us are a, b, c, and pq.

9
00:00:28,810 --> 00:00:31,540
And we need to convert ABC to PQ.

10
00:00:31,540 --> 00:00:39,670
So initially we are going to compare the characters at index zero and zero respectively in ABC and PQ.

11
00:00:39,700 --> 00:00:45,250
So we would make a function call and the inputs would be zero comma zero.

12
00:00:45,340 --> 00:00:48,400
And we see that these two are not equal.

13
00:00:48,400 --> 00:00:52,900
Therefore we would have to compute insert, delete and replace.

14
00:00:52,900 --> 00:00:59,440
We have discussed previously that in the case of insert we would only move the second index, which

15
00:00:59,440 --> 00:01:00,220
is one.

16
00:01:00,220 --> 00:01:04,000
So this zero is zero itself and this zero has become one.

17
00:01:04,000 --> 00:01:05,380
Now why is that the case.

18
00:01:05,380 --> 00:01:06,850
Let's quickly review it.

19
00:01:06,850 --> 00:01:08,950
So we have ABC and PQ.

20
00:01:08,950 --> 00:01:11,260
And we see that these two are not equal.

21
00:01:11,260 --> 00:01:13,420
And we are inserting P over here.

22
00:01:13,540 --> 00:01:16,090
So this pointer stays over here.

23
00:01:16,090 --> 00:01:18,520
And only this pointer has to be moved.

24
00:01:18,520 --> 00:01:21,700
And then next we would want to compare these two characters.

25
00:01:21,700 --> 00:01:26,020
So that's why we only move the second pointer in this case.

26
00:01:26,050 --> 00:01:29,860
Now for delete again we have ABC and PQ.

27
00:01:30,130 --> 00:01:32,080
We see these two are not equal.

28
00:01:32,080 --> 00:01:34,390
And we delete this character.

29
00:01:34,390 --> 00:01:36,940
Now we would have to move this pointer.

30
00:01:36,940 --> 00:01:39,370
So that's why this zero becomes one.

31
00:01:39,370 --> 00:01:41,980
And this stays over here itself.

32
00:01:41,980 --> 00:01:44,320
So this zero is zero itself.

33
00:01:44,320 --> 00:01:48,820
And then finally for replace we have ABC and PQ.

34
00:01:48,850 --> 00:01:50,770
We see these two are not equal.

35
00:01:50,770 --> 00:01:54,010
So this A is replaced and we have P over here.

36
00:01:54,040 --> 00:01:58,900
Now these two are equal and therefore both pointers would have to be moved.

37
00:01:58,900 --> 00:02:02,380
So zero zero becomes one comma one for replace.

38
00:02:03,030 --> 00:02:07,860
Now let's continue and see how the recursion tree looks like.

39
00:02:07,860 --> 00:02:09,360
So over here we have zero one.

40
00:02:09,360 --> 00:02:11,940
So we are comparing this and this.

41
00:02:11,940 --> 00:02:14,130
Again we see that these are not equal.

42
00:02:14,130 --> 00:02:19,470
And we would need to do three calls insert delete and replace.

43
00:02:19,590 --> 00:02:24,300
When we insert we only change the second pointer.

44
00:02:24,300 --> 00:02:26,760
So over here this becomes zero comma two.

45
00:02:26,790 --> 00:02:29,760
For deleting we only change the first pointer.

46
00:02:29,760 --> 00:02:31,650
So this becomes one comma one.

47
00:02:31,650 --> 00:02:35,190
And for replace we have to increment both the pointers.

48
00:02:35,190 --> 00:02:37,140
So this becomes one comma two.

49
00:02:37,140 --> 00:02:39,270
Now let's continue with this branch.

50
00:02:39,270 --> 00:02:41,310
So over here we have one comma one.

51
00:02:41,310 --> 00:02:43,740
Again we see that these are not equal.

52
00:02:43,740 --> 00:02:48,420
So we would have to do three calls insert delete and replace.

53
00:02:48,420 --> 00:02:50,220
And over here we have two comma one.

54
00:02:50,220 --> 00:02:54,540
And again notice that we would have to do insert delete and replace.

55
00:02:54,540 --> 00:02:59,730
And at this point we would start returning because this is out of bound.

56
00:02:59,730 --> 00:03:01,620
This is the last valid character over here.

57
00:03:01,620 --> 00:03:03,870
Over here also we have three which is greater than two.

58
00:03:03,870 --> 00:03:06,750
And over here we have two which is greater than one.

59
00:03:06,750 --> 00:03:10,950
So all of this would return and there would be no level further down.

60
00:03:10,950 --> 00:03:16,890
So the maximum depth that you can see in this recursion tree is equal to five.

61
00:03:16,890 --> 00:03:19,200
So that's 12345.

62
00:03:19,200 --> 00:03:25,650
And this five over here is the sum of the lengths of these two strings over here which is three plus

63
00:03:25,650 --> 00:03:26,010
two.

64
00:03:26,010 --> 00:03:31,770
So the maximum depth of the recursion tree is three plus two which is equal to five.

65
00:03:31,770 --> 00:03:39,450
And therefore the space complexity of this solution is going to be of the order of n plus m, where

66
00:03:39,450 --> 00:03:44,190
n and m are the lengths of word one and word two, respectively.

67
00:03:44,190 --> 00:03:51,570
So again, the space complexity is of the order of n plus m, because we will be using up space on the

68
00:03:51,570 --> 00:03:52,980
recursive call stack.

69
00:03:53,070 --> 00:03:55,230
Now what about the time complexity?

70
00:03:55,230 --> 00:04:02,700
The time complexity is going to be of the order of three to the power n plus m, because in each level,

71
00:04:02,700 --> 00:04:09,000
in the worst case, we have three times the number of nodes that are there in the previous level.

72
00:04:09,000 --> 00:04:11,160
For example, over here we had one node.

73
00:04:11,160 --> 00:04:14,130
Node is that in the next level we are having three nodes.

74
00:04:14,130 --> 00:04:21,630
So in the worst case every subsequent level has three x the number of nodes as the previous level.

75
00:04:21,630 --> 00:04:27,240
And that's why the time complexity is of the order of three to the power n plus m.

76
00:04:27,240 --> 00:04:33,360
Notice that this is pretty much similar to the way that we discussed the time complexity for the Fibonacci

77
00:04:33,360 --> 00:04:36,840
question, where we implemented a recursive solution.