1
00:00:00,180 --> 00:00:10,500
OK, so now that we have gone over how to solve for the time complexity of iterative algorithms, it

2
00:00:10,500 --> 00:00:15,960
is time for us to look at how to do the same for recursive algorithms.

3
00:00:17,010 --> 00:00:23,970
So I know we didn't go super deep on the iterative algorithms, and I'm not going to go super deep on

4
00:00:23,970 --> 00:00:33,750
the recursive version today, but I will be including more examples after this.

5
00:00:34,170 --> 00:00:41,220
The last lecture and this lecture and kind of just meant to introduce you to the tools that we use to

6
00:00:41,220 --> 00:00:44,310
do these more formal analysis of algorithms.

7
00:00:44,310 --> 00:00:50,940
So we'll I'll give some examples of some more difficult summations and things and some more difficult

8
00:00:52,470 --> 00:00:53,980
recursion things.

9
00:00:54,090 --> 00:01:00,000
We're going to talk about today after these two lectures, so you will have a chance to practice similar.

10
00:01:00,180 --> 00:01:04,290
So with that, let's get into how to solve for recursive algorithms.

11
00:01:05,690 --> 00:01:08,160
So how do we analyze recursive algorithms?

12
00:01:08,180 --> 00:01:12,890
Well, rather than just using the summations that we used before, we can use something that better

13
00:01:12,890 --> 00:01:16,340
models the recursive pattern to solve for the time complexity.

14
00:01:17,150 --> 00:01:22,370
And so a useful method for this is to use something called a recurrence relation.

15
00:01:22,910 --> 00:01:25,250
And an example of recurring insulation.

16
00:01:25,250 --> 00:01:26,810
Is this right here?

17
00:01:27,260 --> 00:01:31,460
So this might look a little scary if you don't like math stuff.

18
00:01:31,460 --> 00:01:37,360
But don't worry, we're going to go over this example, the rest of the slide show.

19
00:01:37,370 --> 00:01:41,300
And so we will look at it in quite a bit of detail, which will help you understand.

20
00:01:42,590 --> 00:01:44,360
So let's dissect that example.

21
00:01:44,360 --> 00:01:52,940
I'm using some color coded pieces of the formula and relating it to the explanation just so we can understand

22
00:01:52,940 --> 00:01:54,800
the connection between the two.

23
00:01:55,610 --> 00:02:03,350
So here we're asking how much time is taken to solve a problem of size and that's represented with the

24
00:02:03,350 --> 00:02:04,510
yellow T event.

25
00:02:04,520 --> 00:02:06,830
So the T is for the time taken.

26
00:02:07,220 --> 00:02:10,970
And in the parentheses for a problem the size of an.

27
00:02:12,380 --> 00:02:18,170
And that is when the problem has a recursive call that reduces the size of the input by one.

28
00:02:19,270 --> 00:02:24,430
So that would be this green thing right here, that's the recursive call, reducing the size of the

29
00:02:24,440 --> 00:02:25,240
input by one.

30
00:02:26,790 --> 00:02:31,920
And there's a single instance of our chosen basic operation, which is plus one that happens each time

31
00:02:31,920 --> 00:02:32,700
the function is called.

32
00:02:33,330 --> 00:02:35,480
So this is our basic operation.

33
00:02:35,490 --> 00:02:41,670
As you'll see in the next slide, I came up with the code that goes with this recurrence relation.

34
00:02:41,670 --> 00:02:47,960
There could be multiple functions and multiple pieces of code that might relate to this recurrence relation,

35
00:02:47,970 --> 00:02:52,050
but I have an example in the next slide and that I've chosen multiplication.

36
00:02:52,050 --> 00:02:54,060
So we're just choosing a basic operation.

37
00:02:54,060 --> 00:03:00,060
And this red thing is representing the basic operations, the number of basic operations that we're

38
00:03:00,060 --> 00:03:02,370
adding per call of the function.

39
00:03:04,010 --> 00:03:08,770
We also note that the time taken to solve a problem of size zero is zero.

40
00:03:08,810 --> 00:03:10,600
So that is our base case right here.

41
00:03:10,610 --> 00:03:17,630
So T for time taken to solve the problem of size zero here in the parentheses is equal to zero basic

42
00:03:17,630 --> 00:03:18,570
operations.

43
00:03:18,590 --> 00:03:20,840
And so let's see why that is.

44
00:03:21,080 --> 00:03:21,890
In the next slide.

45
00:03:23,290 --> 00:03:30,110
So here I have a function called Ecsponent, and all it really does is take a number and raise it to

46
00:03:30,110 --> 00:03:38,080
the in power, which is also passed as an argument, and it does that by recursively calling the function

47
00:03:38,080 --> 00:03:44,710
and multiplying acts with itself, basically and then as a base case, if any, zero return one.

48
00:03:45,550 --> 00:03:48,370
So look back at our recurring situation here.

49
00:03:48,520 --> 00:03:50,230
We live in minus one in the green.

50
00:03:50,230 --> 00:03:52,930
Right here is our recursive call we were talking about.

51
00:03:53,620 --> 00:03:58,420
The plus one is for this basic operation, which is multiplication.

52
00:03:58,420 --> 00:04:00,880
That is just what I chose for this.

53
00:04:01,480 --> 00:04:06,670
I chose to solve for the number of multiplications in this algorithm.

54
00:04:06,670 --> 00:04:11,410
And so that is what I'm considering for the time complexity I have chosen the basic operation, its

55
00:04:11,410 --> 00:04:12,370
multiplication.

56
00:04:12,850 --> 00:04:18,280
And so that's why there's this plus one right there because we have one multiplication.

57
00:04:20,470 --> 00:04:28,630
And the base case of zero is right here, so if an equal zero, if the input size of the size of the

58
00:04:28,630 --> 00:04:34,280
problem is zero, then there will be zero multiplications.

59
00:04:34,360 --> 00:04:34,610
Right.

60
00:04:34,630 --> 00:04:38,770
Because we chose the multiplication operation and there's no modifications here.

61
00:04:39,130 --> 00:04:40,360
So I'm putting zero.

62
00:04:40,780 --> 00:04:47,110
You might be thinking, OK, well, this is a constant operation, so we could be adding this and you

63
00:04:47,110 --> 00:04:47,560
could.

64
00:04:47,680 --> 00:04:49,510
But like I said, I chose modification.

65
00:04:49,510 --> 00:04:53,070
So I'm counting the counting, the number of multiplications.

66
00:04:53,440 --> 00:05:01,990
And even if you did have you know this to be one, you would still end up with a similar time complexity

67
00:05:01,990 --> 00:05:06,220
and we could maybe look at that at the end of the lecture.

68
00:05:06,420 --> 00:05:10,720
But for this problem, at least you would turn out at the same time complexity.

69
00:05:10,720 --> 00:05:11,020
So.

70
00:05:12,450 --> 00:05:18,390
But we're just looking at T zero zero because we care about loan applications right now, so to solve

71
00:05:18,390 --> 00:05:22,770
this recurrent solution, we're going to use some simple repetition and substitution until we can find

72
00:05:22,770 --> 00:05:23,430
a pattern.

73
00:05:24,270 --> 00:05:28,890
Then we'll use that pattern to come up with a better formula to solve for the time complexity of the

74
00:05:28,890 --> 00:05:29,550
algorithm.

75
00:05:29,560 --> 00:05:36,630
So if we take a look back at recursion, basically what we were doing in recursion and needing to keep

76
00:05:36,630 --> 00:05:42,180
breaking the problem into smaller and smaller problem until we reach our base case, and then that means

77
00:05:42,180 --> 00:05:43,260
that we need to.

78
00:05:43,530 --> 00:05:50,040
We then have the means to go back and solve our original problem once we know the base case.

79
00:05:50,940 --> 00:05:57,450
So an example of what I mean by this in relation to our recurrent formula here is I'm looking at T of

80
00:05:57,450 --> 00:05:58,620
N right now.

81
00:05:59,590 --> 00:06:06,850
T event equals this, but it would be like asking the question, well, what is T of N minus one?

82
00:06:07,930 --> 00:06:12,370
Instead of to give in and that that's what we're going to do, we're going to kind of keep repeatedly

83
00:06:12,370 --> 00:06:14,140
asking this question as we.

84
00:06:15,240 --> 00:06:21,210
Ripley, substitute things into this formula, we keep asking what is TV minus one, what is tier one

85
00:06:21,210 --> 00:06:22,380
less than that, you know?

86
00:06:22,920 --> 00:06:25,750
And so let's go ahead and start out.

87
00:06:25,770 --> 00:06:32,880
So we're going to substitute minus one for in in this so we can ask ourselves what is T minus two minus

88
00:06:32,880 --> 00:06:33,120
one?

89
00:06:34,840 --> 00:06:39,950
So I have put the original formula up here and read just to have it as reference.

90
00:06:40,510 --> 00:06:44,650
And I'll be doing that in the next few slides as well, so we'll be able to refer back to that.

91
00:06:45,820 --> 00:06:53,410
So here we are, substituting and minus one into our original formula, so we have T minus one instead

92
00:06:53,410 --> 00:06:55,720
of in and we've substituted here in green.

93
00:06:55,930 --> 00:07:04,570
You can see and that ended up giving us a result of of a minus one is equal to T of minus two plus one

94
00:07:04,810 --> 00:07:06,280
because we have these two minus ones there.

95
00:07:07,570 --> 00:07:08,800
So we want to know what you mean.

96
00:07:08,800 --> 00:07:13,090
Minus one was then we substituted for in and we ended up with these two right here.

97
00:07:13,450 --> 00:07:16,060
So great that we got that.

98
00:07:16,060 --> 00:07:17,530
What do we do now?

99
00:07:17,920 --> 00:07:20,350
Well, we now know what you mean.

100
00:07:20,350 --> 00:07:32,620
Minus one is so what we can do is substituted back into the Formula T of in where we left off and simplify.

101
00:07:33,370 --> 00:07:41,230
So since we owe to you and minus one is this we can replace DeHaven minus one or we left off with this

102
00:07:41,470 --> 00:07:45,910
light blue right here because that's what we figured out in the previous slide.

103
00:07:47,660 --> 00:07:53,210
And if we simplify that, it gives us T minus two plus two.

104
00:07:54,740 --> 00:07:55,730
So what do we do now?

105
00:07:55,760 --> 00:07:58,250
Well, we just continue this process, actually.

106
00:07:58,400 --> 00:08:04,520
We're going to keep asking, well, what is one less again?

107
00:08:04,520 --> 00:08:06,380
So we said T minus one.

108
00:08:06,380 --> 00:08:10,540
We wanted to know that now we're at T-minus two.

109
00:08:10,550 --> 00:08:13,760
So let's ask the question, well, what is T then minus two?

110
00:08:13,760 --> 00:08:15,800
And then we're going to try and solve for that.

111
00:08:16,690 --> 00:08:19,510
So let's try and solve for T of and minus two.

112
00:08:22,440 --> 00:08:23,790
So here's our original formula.

113
00:08:23,940 --> 00:08:27,420
This is where we left off, we said TV Nichols TV minus two plus two.

114
00:08:28,200 --> 00:08:33,300
So what we're going to do is substitute in minus two in our original formula now.

115
00:08:34,750 --> 00:08:37,600
So putting in minus two instead of in.

116
00:08:37,990 --> 00:08:42,280
And that gives us T minus three plus one.

117
00:08:43,480 --> 00:08:49,060
And then just like before, we're going to take that answer and we're going to substitute where we left

118
00:08:49,060 --> 00:08:49,330
off.

119
00:08:50,260 --> 00:08:51,670
So we're at this point right here.

120
00:08:51,670 --> 00:08:55,210
So now we we know what T of in minus two is.

121
00:08:55,720 --> 00:08:57,460
You can imagine that's right here, too.

122
00:08:57,460 --> 00:09:02,920
I just put this equals sign saying no to unless two equals this and then we simplify it.

123
00:09:02,920 --> 00:09:03,910
And so it was this.

124
00:09:03,910 --> 00:09:06,220
So this is T even minus two.

125
00:09:06,880 --> 00:09:10,900
And now that we have that, we're able to substitute it.

126
00:09:10,900 --> 00:09:15,100
We don't need this to even minus two more, we because we have this now so we can continue on.

127
00:09:15,110 --> 00:09:16,990
So I'm replacing.

128
00:09:18,150 --> 00:09:23,040
TV minus two with this blu ray here, which is this.

129
00:09:24,180 --> 00:09:25,590
And that's what you see right here.

130
00:09:26,130 --> 00:09:30,570
And then we simplify that, and it simplifies to TV minus three plus three.

131
00:09:32,000 --> 00:09:34,100
So let's continue on the time.

132
00:09:35,360 --> 00:09:41,210
So original formula up here, this is where we left off right now, we're going to say, Hey, what

133
00:09:41,210 --> 00:09:42,260
is TV minus three?

134
00:09:42,260 --> 00:09:43,190
Let's figure that out.

135
00:09:43,610 --> 00:09:44,960
So TV minus three.

136
00:09:45,960 --> 00:09:48,870
It's basically here we're doing it in our original formula.

137
00:09:49,890 --> 00:09:52,470
So we're seeing in minus three instead of in.

138
00:09:52,770 --> 00:09:54,810
So T of minus three, minus one.

139
00:09:55,350 --> 00:09:56,700
That's going to be a minus four.

140
00:09:56,940 --> 00:09:58,170
And then we have the plus one.

141
00:09:58,170 --> 00:09:59,640
So we're substituting minus three.

142
00:09:59,640 --> 00:10:00,360
We end up with this.

143
00:10:01,600 --> 00:10:05,680
And then that next type of substitution where we use this blue.

144
00:10:06,690 --> 00:10:11,790
We're basically going to go where we left off in the formula for Kevin, which is right here.

145
00:10:13,250 --> 00:10:21,650
And we are going to substitute this answer we got right here, so TVN minus four plus one in the formula

146
00:10:21,650 --> 00:10:22,340
where we left off.

147
00:10:22,640 --> 00:10:23,600
That gives us.

148
00:10:23,690 --> 00:10:25,190
We have this one in the story here.

149
00:10:25,550 --> 00:10:27,380
TVN minus four plus four.

150
00:10:29,360 --> 00:10:31,970
And so maybe you don't see a pattern.

151
00:10:32,030 --> 00:10:35,990
Maybe you do already see a pattern, but that's what we're going to look into now.

152
00:10:36,260 --> 00:10:41,480
So what we're interested in is finding a pattern for something we call the eighth term.

153
00:10:42,260 --> 00:10:48,530
And what that is is basically just taking a look at all of the results of the blue substitutions we

154
00:10:48,530 --> 00:10:49,160
were doing.

155
00:10:49,940 --> 00:10:52,090
So those again, the results were yellow.

156
00:10:52,100 --> 00:10:53,810
So I'm going back one slide.

157
00:10:54,290 --> 00:10:58,640
I'm talking about this substitution when we substituted these blue things in the formula here where

158
00:10:58,640 --> 00:11:00,920
we sold for it and it gave us these results.

159
00:11:01,280 --> 00:11:04,670
This is kind of where we keep saying, Oh, where we left off, where we left off.

160
00:11:05,000 --> 00:11:07,940
Now we're at this point, this is where we left off last.

161
00:11:09,260 --> 00:11:10,970
So we look at all those yellow guys there.

162
00:11:12,680 --> 00:11:17,690
We're basically trying to look through all of those, so we start at the beginning, this is our original

163
00:11:17,690 --> 00:11:18,220
formula.

164
00:11:18,230 --> 00:11:22,310
Then we had and minus two plus two and minus three plus three and four plus two.

165
00:11:22,430 --> 00:11:29,960
We want to find a generalization of the pattern and put it in terms of AI so that you might be able

166
00:11:29,960 --> 00:11:31,220
to see a pattern here.

167
00:11:32,570 --> 00:11:33,470
And I definitely do.

168
00:11:33,470 --> 00:11:36,330
And on the next slide, I'm going to show you what that is either.

169
00:11:37,700 --> 00:11:43,490
So instead of just two and two and three and three and three and four four, I notice these are the

170
00:11:43,490 --> 00:11:44,060
same numbers.

171
00:11:44,070 --> 00:11:49,760
So what I'm going to do is actually just say teven minus AI plus I.

172
00:11:51,180 --> 00:11:58,740
So you can imagine that, like if we're on this ice iteration of us doing the recursive process, you

173
00:11:58,740 --> 00:12:01,710
know, we had one and then we had to.

174
00:12:01,890 --> 00:12:04,710
So our I was two and I was three and I was four.

175
00:12:05,980 --> 00:12:10,270
Basically, I can say, you know, when I was two, when we were on our second.

176
00:12:11,170 --> 00:12:16,360
Kind of repetition of this whole process of substitution.

177
00:12:17,420 --> 00:12:20,130
And I was to say a second repetition of this whole process.

178
00:12:20,180 --> 00:12:24,230
Then it was also a two right here and a two right here.

179
00:12:24,530 --> 00:12:32,030
So I'm going to say when we're on the eighth repetition of this process, I can basically say that there's

180
00:12:32,030 --> 00:12:35,990
going to be an eye here and here, and I make this generalized formula.

181
00:12:37,600 --> 00:12:41,660
And so great now we have this generalized formula, so what's the really the point?

182
00:12:41,680 --> 00:12:42,530
How does that help us?

183
00:12:42,550 --> 00:12:48,130
Well, what we're going to do now is actually get back to our base case.

184
00:12:48,130 --> 00:12:50,020
So let's think about our base case.

185
00:12:50,020 --> 00:12:52,530
So I've kind of been putting that off sometime.

186
00:12:52,540 --> 00:12:53,680
You noticed it was right here.

187
00:12:54,870 --> 00:12:58,800
But we've kind of just been solving and messing with this stuff right here.

188
00:12:59,490 --> 00:13:02,310
Now we're going to look at this T of zero equals zero.

189
00:13:03,150 --> 00:13:11,550
So what I want to do is use this base case in conjunction with our new iith term to see if I can get

190
00:13:11,550 --> 00:13:21,030
the IV term back in terms of in because we really want to solve for N in the end, because we were interested

191
00:13:21,030 --> 00:13:25,290
in the time taken to solve the problem with an input end.

192
00:13:25,410 --> 00:13:28,170
Remember, that's what we originally asked.

193
00:13:28,740 --> 00:13:36,630
So now what we're going to do is use this base case to help us get this right here back into terms of

194
00:13:36,630 --> 00:13:40,470
n so we can finally solve for our overall time complexity.

195
00:13:41,790 --> 00:13:47,490
And so what I'm going to do is I may say, OK, well, this is T of zero when the problem size is zero

196
00:13:47,490 --> 00:13:52,200
and I'm just going to I know that what's in the parentheses here can be considered when the problem

197
00:13:52,200 --> 00:13:55,890
size is, you know, the eighth term.

198
00:13:55,890 --> 00:14:00,900
And so what I can actually do is, I can say in minus II is equal to zero.

199
00:14:01,380 --> 00:14:03,630
I can assume we're at the base case.

200
00:14:04,870 --> 00:14:12,520
Right, so I can assume, OK, I'm going to go ahead and say that we are at a point in time when the

201
00:14:12,520 --> 00:14:16,900
problem size is zero because we know what that is.

202
00:14:17,260 --> 00:14:21,490
And so I'm going to say, all right, well, then n minus II equals zero.

203
00:14:23,370 --> 00:14:26,850
So what I can do then to get it in terms of in.

204
00:14:27,830 --> 00:14:33,050
Is I can simplify this by not really simple, I would rearrange it, I can add I on this side and I

205
00:14:33,050 --> 00:14:34,070
on this side too.

206
00:14:34,880 --> 00:14:36,860
And then we get something in equals.

207
00:14:36,860 --> 00:14:44,350
I know now we basically can put it in terms of in right because we found out that I not only is an equal

208
00:14:44,350 --> 00:14:46,040
to I, but it goes this way too, of course.

209
00:14:46,040 --> 00:14:47,120
So I equals in.

210
00:14:47,510 --> 00:14:49,380
I can replace these ideas within.

211
00:14:49,490 --> 00:14:50,780
So let's go ahead and do that now.

212
00:14:50,780 --> 00:14:54,260
We substitute in for AI and our generalized AI term formula.

213
00:14:55,490 --> 00:15:00,620
So T event equals T of N minus N instead of AI plus N instead of AI.

214
00:15:01,550 --> 00:15:03,260
And you might see this right here.

215
00:15:04,500 --> 00:15:07,900
And minus in something minus itself is zero.

216
00:15:08,520 --> 00:15:10,980
That's pretty interesting because we know this right here.

217
00:15:13,000 --> 00:15:16,330
So if we have that, this is kind of just a little recap right here.

218
00:15:17,230 --> 00:15:23,290
But if we know that, then we can say, OK, well, that's T of zero right says to zero plus in, oh,

219
00:15:23,290 --> 00:15:25,640
well, remember, let's jump back here.

220
00:15:25,960 --> 00:15:28,090
Our base case T of zero, we know what that is.

221
00:15:28,090 --> 00:15:28,750
It's zero.

222
00:15:29,650 --> 00:15:34,960
So instead of putting T of zero here, we can just substitute two zero four two zero because that's

223
00:15:34,960 --> 00:15:35,500
what it is.

224
00:15:35,500 --> 00:15:38,590
We we we know that that's our base case two zero zero zero.

225
00:15:39,370 --> 00:15:42,190
When we do that, we're left with just here then equals in.

226
00:15:42,910 --> 00:15:45,490
And at this point since we just have to then equals.

227
00:15:45,490 --> 00:15:48,100
And that was what we were asking in the beginning, right?

228
00:15:48,490 --> 00:15:50,770
How much time did it take to?

229
00:15:51,880 --> 00:15:55,390
How much time does it take when the input is in?

230
00:15:55,390 --> 00:15:57,300
You know, the problem size is in.

231
00:15:58,270 --> 00:16:01,900
And right here T of any equals in, that's a solid answer.

232
00:16:02,200 --> 00:16:08,890
Now we can actually say that we have an exact bound on this area and we can say that the time taken

233
00:16:08,890 --> 00:16:09,810
is theta.

234
00:16:10,130 --> 00:16:12,250
And so we have a tight bound.

235
00:16:13,400 --> 00:16:21,890
And so, you know that if we have a tape bound on this, then we also could potentially say big, oh,

236
00:16:21,890 --> 00:16:22,790
you know, we kind of.

237
00:16:24,250 --> 00:16:26,920
You know, state is a little better because it's a more exact bound.

238
00:16:27,070 --> 00:16:31,330
But if we wanted to, we could also say Big O event, right?

239
00:16:31,340 --> 00:16:39,070
Because if you think back to how we were bounding the functions and that lecture, we said that the

240
00:16:39,070 --> 00:16:46,720
Big O was an upper bound and so it was greater than or equal to the function and consideration.

241
00:16:47,350 --> 00:16:51,610
And the key is equal to, you know, greater than or equal to.

242
00:16:51,610 --> 00:16:58,840
And so since this is a time bound, you know, we could also say that it's big of an because the tie

243
00:16:58,840 --> 00:16:59,880
bound is something equal.

244
00:16:59,900 --> 00:17:03,430
You know, it's it's a it's a tie bound is bounded upper and lower.

245
00:17:03,430 --> 00:17:06,130
So we could also see a big event.

246
00:17:06,130 --> 00:17:07,910
But this is kind of nicer to have Theta.

247
00:17:07,950 --> 00:17:12,730
And so hopefully that helps connect our bound to that a little bit.

248
00:17:12,730 --> 00:17:19,120
And hopefully this was enough to explained the general way of solving these recurrent relations.

249
00:17:19,720 --> 00:17:21,990
And like I said, we will do some more examples.

250
00:17:22,000 --> 00:17:27,370
I'm going to go ahead and write some up so you can look over those and I'll have some notes that way.

251
00:17:27,370 --> 00:17:32,030
You can see some other solutions for some slightly more difficult ones.

252
00:17:32,050 --> 00:17:36,700
This was a pretty basic one right here, and I'll try and do some for some patients, too.

253
00:17:36,700 --> 00:17:39,430
But with that, I will see you in the next lecture.