1
00:00:00,460 --> 00:00:02,320
Hey there and welcome back!

2
00:00:02,350 --> 00:00:08,710
Previously we have discussed the recursive approach and we have also discussed the pseudocode for the

3
00:00:08,710 --> 00:00:09,700
recursive approach.

4
00:00:09,730 --> 00:00:16,690
Now let's go ahead and draw the recursion tree and then discuss the complexity analysis for the approach

5
00:00:16,690 --> 00:00:17,680
that we have come up with.

6
00:00:17,680 --> 00:00:20,860
So let's get started with drawing the recursion tree.

7
00:00:21,520 --> 00:00:27,670
So for this let's take an example where the two strings are a, b, c and a c.

8
00:00:27,760 --> 00:00:34,180
When we start with the algorithm, we will notice that these two characters are equal or they are the

9
00:00:34,180 --> 00:00:34,690
same.

10
00:00:34,690 --> 00:00:40,210
Therefore, we would call the recursive function for the remaining parts over here.

11
00:00:40,210 --> 00:00:46,480
So the answer would be one plus the answer to the subproblem which is b, c, and c.

12
00:00:46,660 --> 00:00:52,960
Now after this, when we are comparing these two characters, we see that they are not equal.

13
00:00:52,960 --> 00:00:56,740
So we have to find the maximum between two calls.

14
00:00:56,740 --> 00:01:04,210
So in one call we would keep this index over here itself and increment this index to the next place.

15
00:01:04,210 --> 00:01:09,400
So the call becomes b c and nothing because over here there's nothing after c.

16
00:01:09,400 --> 00:01:16,120
And if one of these is empty then we have seen that we would hit the base case and it would just return

17
00:01:16,120 --> 00:01:16,780
zero.

18
00:01:17,450 --> 00:01:23,810
Now, the other call over here would be keeping this over here as it is and incrementing this index

19
00:01:23,810 --> 00:01:25,160
to this place over here.

20
00:01:25,160 --> 00:01:28,130
So the call becomes C and C.

21
00:01:28,130 --> 00:01:33,800
And over here, because these two are equal the answer becomes one plus.

22
00:01:33,800 --> 00:01:37,490
And then we increment both these two nothing and nothing.

23
00:01:37,490 --> 00:01:41,720
And when you don't have anything over here this would just return zero.

24
00:01:41,720 --> 00:01:47,090
Therefore the answer for this sub problem becomes zero plus one which is one.

25
00:01:47,090 --> 00:01:49,040
And that's what is returned over here.

26
00:01:50,380 --> 00:01:54,310
And then between 0 and 1 the maximum is one.

27
00:01:54,310 --> 00:01:57,670
So this subproblem over here will return one.

28
00:01:57,670 --> 00:02:01,180
And then the answer is one plus what we get over here.

29
00:02:01,180 --> 00:02:05,290
So the answer becomes one plus one which is equal to two.

30
00:02:06,560 --> 00:02:12,080
So this is the recursion tree for the recursive approach that we have just now discussed for solving

31
00:02:12,080 --> 00:02:13,370
the LCS problem.

32
00:02:13,400 --> 00:02:20,570
Now let's try to think of what the maximum depth would be, so that we can use that to identify the

33
00:02:20,570 --> 00:02:23,780
space complexity of the approach that we have discussed.

34
00:02:23,780 --> 00:02:31,370
So let's say we have a, b, c and p q as the two strings which are given to us.

35
00:02:31,370 --> 00:02:37,700
So initially we would be calling the recursive function with the indices zero and zero.

36
00:02:37,700 --> 00:02:39,560
So let's write that over here.

37
00:02:39,560 --> 00:02:45,170
And when we do this call we'll see that these two indices are not the same.

38
00:02:45,170 --> 00:02:46,370
They are not equal.

39
00:02:46,370 --> 00:02:52,370
Therefore we would have to do two calls and we would just increment one index in each call.

40
00:02:52,370 --> 00:02:56,480
And that means we will call zero one and one zero.

41
00:02:56,480 --> 00:03:01,760
Now zero one means we keep this index over here itself and we increment it over here.

42
00:03:01,760 --> 00:03:04,400
So this string remains as it is.

43
00:03:04,400 --> 00:03:06,950
And this string becomes just Q.

44
00:03:06,950 --> 00:03:09,020
That's this call over here zero one.

45
00:03:09,020 --> 00:03:11,720
And then we are comparing these two characters.

46
00:03:11,720 --> 00:03:14,570
And we see that they are again not equal.

47
00:03:14,570 --> 00:03:19,520
So we'll have to do two calls and we'll just increment one index at a time.

48
00:03:19,520 --> 00:03:27,020
So one call for solving this becomes zero two where we increment this index and the other call becomes

49
00:03:27,020 --> 00:03:30,230
one one where we only increment this index.

50
00:03:30,590 --> 00:03:37,280
Now this call over here will return zero because notice that the last valid index in the second string

51
00:03:37,280 --> 00:03:37,790
is one.

52
00:03:37,790 --> 00:03:41,420
And we have already got two over here, which is beyond one now.

53
00:03:41,420 --> 00:03:43,160
So this will not go down further.

54
00:03:43,160 --> 00:03:48,830
And then over here we have one comma one where we are dealing with these two substrings.

55
00:03:49,550 --> 00:03:51,920
Again, we see that these two are not equal.

56
00:03:51,920 --> 00:03:55,970
So we'll have to do two calls one comma two and two comma one.

57
00:03:56,120 --> 00:04:01,400
Again, one comma two would return zero because the last valid index over here is one.

58
00:04:01,400 --> 00:04:02,960
But we have two over here.

59
00:04:02,960 --> 00:04:10,730
But for finding two comma one the strings that we are considering are C and q, we again see that these

60
00:04:10,730 --> 00:04:11,900
two are not equal.

61
00:04:11,900 --> 00:04:14,180
And because of that we have to do two calls.

62
00:04:14,180 --> 00:04:18,740
So the two calls that we have to do are two comma two and three comma one.

63
00:04:18,920 --> 00:04:25,340
Now two comma two again will return zero because this index becomes two which is greater than this one.

64
00:04:25,340 --> 00:04:32,000
And over here three comma one also will return zero because we have three over here which is greater

65
00:04:32,000 --> 00:04:34,400
than the last valid index which is two.

66
00:04:34,430 --> 00:04:37,550
Now let's go ahead and complete this branch as well.

67
00:04:37,550 --> 00:04:45,530
So the strings that we are considering over here are b, c and p q because we have one comma zero and

68
00:04:45,530 --> 00:04:52,070
because b and p are not equal, we will again have to do two calls where we increment only one index

69
00:04:52,070 --> 00:04:52,820
at a time.

70
00:04:52,820 --> 00:04:57,950
So the two calls are one comma one and two comma zero and one comma one.

71
00:04:57,950 --> 00:05:01,340
Is this part where we are considering b, c and q.

72
00:05:01,340 --> 00:05:04,160
Notice that again b and q are not equal.

73
00:05:04,160 --> 00:05:10,730
So we'll have to do two calls which is one comma two and two comma one and one comma two will return

74
00:05:10,730 --> 00:05:16,430
zero because two is greater than the last valid index over here, which is one and two comma one.

75
00:05:16,430 --> 00:05:20,810
Again, when we're dealing with two comma one, we are dealing with c and q.

76
00:05:20,810 --> 00:05:22,790
Now these two are not equal.

77
00:05:22,790 --> 00:05:26,750
So we will have to do two calls two comma two and three comma one.

78
00:05:26,750 --> 00:05:30,470
And these two will again return zero because this is beyond one.

79
00:05:30,470 --> 00:05:32,960
And this three over here is beyond this two.

80
00:05:33,290 --> 00:05:36,110
Now let's go ahead and complete this branch over here.

81
00:05:36,110 --> 00:05:38,420
Now to find two comma zero.

82
00:05:38,420 --> 00:05:42,500
The substrings that we are considering are c and p q.

83
00:05:42,650 --> 00:05:45,380
Again we see that c and p are not equal.

84
00:05:45,380 --> 00:05:51,230
Now because of that we have to do two calls where we will be incrementing one index at a time.

85
00:05:51,230 --> 00:05:54,050
So we get two comma one and three comma zero.

86
00:05:54,050 --> 00:06:00,050
Now three comma zero will return zero because three is beyond two, which is the last valid index over

87
00:06:00,050 --> 00:06:00,500
here.

88
00:06:00,500 --> 00:06:05,000
And to find two comma one again we're dealing with c and q.

89
00:06:05,000 --> 00:06:07,310
And these characters are not equal.

90
00:06:07,310 --> 00:06:11,450
So we will have to do two calls two comma two and three comma one.

91
00:06:11,450 --> 00:06:13,400
And these two will return zero.

92
00:06:13,400 --> 00:06:20,810
Now our intention for drawing this was to identify the maximum depth in the recursion tree, because

93
00:06:20,810 --> 00:06:25,700
that would help us identify the recursive call stack space that we are using.

94
00:06:25,700 --> 00:06:32,900
So notice over here that the maximum depth is equal to 512345.

95
00:06:32,900 --> 00:06:36,320
And over here the lengths were two and three.

96
00:06:36,320 --> 00:06:40,790
And this five over here is actually two plus three right.

97
00:06:40,790 --> 00:06:41,540
So this is three.

98
00:06:41,540 --> 00:06:42,770
The length over here is three.

99
00:06:42,770 --> 00:06:44,600
And over here the length is two.

100
00:06:44,600 --> 00:06:47,840
And that's why the maximum depth is five.

101
00:06:47,840 --> 00:06:50,660
Because we are only changing one index at a time.

102
00:06:50,660 --> 00:06:56,330
So over here notice we we kept going down down down till we reached over here.

103
00:06:56,330 --> 00:07:00,800
Because over here this index is out of scope and therefore it will return zero.

104
00:07:00,800 --> 00:07:06,140
Notice that in none of the previous calls over here did we hit the base case.

105
00:07:06,140 --> 00:07:08,630
So we have to go down till over here.

106
00:07:08,630 --> 00:07:10,430
And this is the maximum depth.

107
00:07:10,430 --> 00:07:12,830
Now there are branches with lesser depth.

108
00:07:12,830 --> 00:07:19,220
But the maximum depth helps us identify the upper bound of the space complexity or the space used on

109
00:07:19,220 --> 00:07:20,600
the recursive call stack.

110
00:07:20,600 --> 00:07:26,900
And therefore the space complexity of this solution is of the order of n plus m.

111
00:07:27,140 --> 00:07:29,510
Now what about the time complexity?

112
00:07:29,510 --> 00:07:36,410
The time complexity of this solution is going to be of the order of two to the power n plus m, which

113
00:07:36,410 --> 00:07:42,350
can be thought of as two into two, into two, etc. n plus m times.

114
00:07:42,440 --> 00:07:48,140
Think of the Fibonacci question that we have done and the time complexity that we are getting over here.

115
00:07:48,140 --> 00:07:54,620
And the way that we get this is very much similar to how we identified the time complexity of the recursive

116
00:07:54,620 --> 00:07:57,140
solution for the Fibonacci question.

117
00:07:57,140 --> 00:08:04,640
Now, again, you can think of it as every level has two x nodes as the previous level, and there are

118
00:08:04,640 --> 00:08:06,800
at max n plus m levels.

119
00:08:06,800 --> 00:08:14,660
So the maximum or the upper bound of the time complexity is two to the power n plus m, or the maximum

120
00:08:14,660 --> 00:08:22,010
number of nodes that can be there in this recursive tree is two to the power n plus m, and in each

121
00:08:22,010 --> 00:08:25,460
node we are just doing constant amount of work.

122
00:08:25,460 --> 00:08:31,940
So that's why the time complexity is of the order of two to the power n plus m into one.

123
00:08:31,940 --> 00:08:35,570
Or we can just say of the order of two to the power n plus m.