1
00:00:00,690 --> 00:00:01,270
OK.

2
00:00:01,440 --> 00:00:07,920
So in this lecture today, we're going to be looking at a recurrence that's very similar to the one

3
00:00:07,920 --> 00:00:09,930
we looked at in the previous lecture.

4
00:00:10,710 --> 00:00:18,450
But we're going to look at a better way to solve it if we have something inside the recurrence called

5
00:00:18,450 --> 00:00:22,320
floor division so we can go over kind of a new rule here today.

6
00:00:23,370 --> 00:00:28,020
So let's revisit a somewhat familiar occurrence, which is the one we talked about in the last lecture

7
00:00:28,950 --> 00:00:31,530
unless actually we had tea event over two plus one.

8
00:00:32,340 --> 00:00:37,770
So this is similar, except it has these floor division operators around it.

9
00:00:37,770 --> 00:00:42,390
So we talked a little bit about using floor division when we're doing our binary search.

10
00:00:42,750 --> 00:00:50,550
But this time we have the actual floor revision present in our recursive call, part of the recursive

11
00:00:50,550 --> 00:00:52,230
call, part of the recurrent solution here.

12
00:00:53,490 --> 00:00:58,050
So this just means that we want to round down to the nearest integer just to remind you of that, that's

13
00:00:58,050 --> 00:00:59,190
what floor division is.

14
00:01:00,670 --> 00:01:04,690
And so you see our base case here as well.

15
00:01:04,960 --> 00:01:11,230
But this kind of makes the recurrence interesting because the math doesn't work out as well as we'd

16
00:01:11,230 --> 00:01:12,640
like for any value in.

17
00:01:12,640 --> 00:01:14,770
So let's look at what we have to do here.

18
00:01:16,430 --> 00:01:20,240
So the problem with this is that it gets a little weird when you think about whether occurrence would

19
00:01:20,240 --> 00:01:25,940
make sense for all values of and if you're substituting, you know, in order to over and over, if

20
00:01:25,940 --> 00:01:30,500
you're thinking about any possible value of in any point in time, it's a little weird with the Florida

21
00:01:30,510 --> 00:01:31,700
vision mathematically.

22
00:01:31,700 --> 00:01:36,980
So a better way to go about solving these recurrences with Florida vision is to use something called

23
00:01:36,980 --> 00:01:37,940
the smoothness rule.

24
00:01:37,940 --> 00:01:39,530
And so that's what we're going to talk about today.

25
00:01:41,060 --> 00:01:47,510
So Smugglers Rule basically says that we can instead assume that N equals two to the K.

26
00:01:48,020 --> 00:01:54,710
That gives us a nice just power of two and that that will give us a correct answer about the order of

27
00:01:54,710 --> 00:01:59,390
growth for all values, events and this kind of like a really broad assumption to smooth this rule.

28
00:02:00,110 --> 00:02:04,220
But people use it, so we introduce it here so it can help us with the currencies.

29
00:02:05,090 --> 00:02:10,240
So, yeah, it just says that that will give us that correct answer for all of then when we're solving

30
00:02:10,250 --> 00:02:11,210
our current situation.

31
00:02:11,210 --> 00:02:12,710
So how do we use that?

32
00:02:14,330 --> 00:02:18,770
So what we can do is actually just make an equal to two to the K.

33
00:02:18,770 --> 00:02:22,960
So instead of us using in all the time, we're going to use two to the K instead.

34
00:02:22,970 --> 00:02:26,330
And since we're doing that, we also need to change our base case here.

35
00:02:26,810 --> 00:02:30,130
So our base case is T of one equals one.

36
00:02:30,140 --> 00:02:35,180
And so since it's one in here, we need to put it in powers of two.

37
00:02:35,330 --> 00:02:39,050
So what we're going to do is, say two to the zero, because two to the zero is one.

38
00:02:39,110 --> 00:02:43,400
So this would be the same thing kind of T of quantity of two zero equals one.

39
00:02:45,570 --> 00:02:51,300
So instead of thinking about doing our normal thing that we were doing like it, it ain't over to over

40
00:02:51,300 --> 00:03:01,110
to to start out, we're instead going to think of this repetitive division as subtracting powers.

41
00:03:01,110 --> 00:03:08,910
So from two to the K, so like two to the K minus one to start out instead of in over two or two.

42
00:03:09,720 --> 00:03:16,770
So if you think about it, if you just do normal exponents like two to three or something like that,

43
00:03:16,770 --> 00:03:21,510
just a positive number is basically a successive multiplication to get to that answer.

44
00:03:22,680 --> 00:03:26,910
So if we want to do this represent the success of division, that's something that's actually more like

45
00:03:26,910 --> 00:03:29,550
subtracting like an exponent.

46
00:03:29,550 --> 00:03:33,360
So, you know, like negative exponents and stuff like that.

47
00:03:33,360 --> 00:03:34,770
So only subtracting exponent.

48
00:03:34,770 --> 00:03:36,930
We can better represent success of division.

49
00:03:36,940 --> 00:03:41,460
And so that's kind of why the smoothness will use this concept right here.

50
00:03:41,790 --> 00:03:43,590
So we're actually going to start out with that.

51
00:03:44,670 --> 00:03:47,280
So let's get started in solving it here.

52
00:03:47,280 --> 00:03:51,690
I'm just doing the same thing I did before, where in red we're just representing our original recurrence

53
00:03:51,690 --> 00:03:52,350
for reference.

54
00:03:53,570 --> 00:03:59,300
And what we're going to do to start out is just do what we said, we're going to substitute in with

55
00:03:59,300 --> 00:04:06,380
two to the K, so if we do that, then we end up with something like this because instead of in over

56
00:04:06,380 --> 00:04:11,570
two, over two, we're actually just going to start out with two to the K minus one.

57
00:04:13,770 --> 00:04:18,840
So what we what we start out with, and I'm going to put this in yellow, because if you remember,

58
00:04:19,800 --> 00:04:24,750
I'm going to kind of highlight all the yellow pieces of this, and that's what we're going to use later

59
00:04:24,750 --> 00:04:26,700
on, define the term.

60
00:04:27,180 --> 00:04:29,940
So that's what the yellow means as we're going through this recurrence.

61
00:04:30,300 --> 00:04:31,360
It's going to eventually.

62
00:04:31,380 --> 00:04:34,980
These are the pieces that we're going to use to find a pattern for the term.

63
00:04:36,570 --> 00:04:41,250
So this is how we start out, you notice we're also doing that substitution here for the base case because

64
00:04:41,250 --> 00:04:43,680
we need to put it in terms of two to the something.

65
00:04:43,680 --> 00:04:45,780
So we're doing that to the zero.

66
00:04:47,220 --> 00:04:52,110
And so let's start out just like we did in the last recurrence, we're going to say, OK, well, what

67
00:04:52,110 --> 00:04:54,010
are we going to do for two to the K minus one?

68
00:04:55,050 --> 00:04:56,280
So let's solve for that.

69
00:04:56,880 --> 00:05:00,000
And when we do that for you two to the K minus one.

70
00:05:01,150 --> 00:05:08,530
Instead of in when we have that over two, we can actually just say two to the K minus two so that we're

71
00:05:08,530 --> 00:05:13,930
just kind of successfully keeps subtracting one each time we're doing another division by two.

72
00:05:13,960 --> 00:05:21,310
You can think of it as you know, an additional, you know, at number here that we're subtracting.

73
00:05:21,310 --> 00:05:24,760
So it came as long as two and so on and so forth.

74
00:05:25,090 --> 00:05:29,590
So think about that repetitive division is now being represented in this manner.

75
00:05:31,100 --> 00:05:35,360
So we end up with this answer for five, for two to the minus one.

76
00:05:35,870 --> 00:05:42,200
So we have this tea of two to the K minus two plus one, and this was our substitution of two to the

77
00:05:42,200 --> 00:05:46,550
K minus one into our original formula.

78
00:05:47,780 --> 00:05:51,950
And then what we're going to do is substitute this whole thing where we left off, which was right here.

79
00:05:52,850 --> 00:05:59,120
So now that we know to to the K minus one, we can substitute this to the K minus one with this whole

80
00:05:59,120 --> 00:05:59,410
thing.

81
00:05:59,420 --> 00:06:00,770
And that's what we're doing down here.

82
00:06:01,490 --> 00:06:06,050
So you notice we put this whole, this whole, this whole thing right here in here.

83
00:06:07,570 --> 00:06:13,840
And we have this extra plus one, so we're simplifying it just t- t- of two to the minus two plus two.

84
00:06:14,860 --> 00:06:18,700
So let's continue on just like we did in the previous slide show.

85
00:06:20,050 --> 00:06:21,490
So this is where we left off.

86
00:06:22,440 --> 00:06:26,400
And now we're going to say, hey, what about T of to the Caymans to.

87
00:06:27,460 --> 00:06:28,810
Well, what is that?

88
00:06:29,590 --> 00:06:33,010
That's actually two to the K minus three plus one here.

89
00:06:33,310 --> 00:06:38,260
So now what we can do after substituting this in the original equation.

90
00:06:41,580 --> 00:06:46,020
We're actually we're just so sorry, we're solving this, so what we want to do after this is now a

91
00:06:46,020 --> 00:06:49,830
substitute, our answer for to the K minus to in the original equation.

92
00:06:49,980 --> 00:06:52,830
So this whole thing is getting substituted here.

93
00:06:53,830 --> 00:06:54,430
For this.

94
00:06:55,390 --> 00:07:00,730
So we had this extra plus two, and now we added this with the plus one, and so if we simplify it,

95
00:07:01,150 --> 00:07:04,390
it's actually going to be two to two to the Chemo's three plus three.

96
00:07:05,260 --> 00:07:09,160
So this was our substitution back into the place that we left off.

97
00:07:12,200 --> 00:07:13,400
All right, cool.

98
00:07:13,640 --> 00:07:19,520
And yeah, when I was saying stuff to you, this in the original equation that that is yes, actually

99
00:07:19,520 --> 00:07:20,100
what I meant.

100
00:07:20,120 --> 00:07:21,650
So you're substituting this for in.

101
00:07:22,100 --> 00:07:23,810
So that's why we ended up with this.

102
00:07:23,810 --> 00:07:25,450
So we seem to have that plus one there.

103
00:07:25,460 --> 00:07:29,990
And if we do two to the K minus two or two in here, it's to the K minus three.

104
00:07:31,370 --> 00:07:32,660
So let's continue on.

105
00:07:32,780 --> 00:07:33,770
This is where we left off.

106
00:07:35,520 --> 00:07:38,670
And now we're going to say, hey, let's find two minus three.

107
00:07:39,210 --> 00:07:42,690
So to the minus three or two to the minus four.

108
00:07:42,780 --> 00:07:46,300
So we're having that plus the one, we get this whole thing.

109
00:07:46,320 --> 00:07:47,410
Let's take this whole thing.

110
00:07:47,430 --> 00:07:49,950
Subs two for two to the K K minus three.

111
00:07:51,100 --> 00:07:53,980
So we do that and we have it in here.

112
00:07:55,020 --> 00:07:58,920
And now we have this three so simple that we have two that came out as four plus four.

113
00:08:00,510 --> 00:08:02,230
OK, so we've gone a few times now.

114
00:08:02,250 --> 00:08:04,050
Let's see if we can find a pattern.

115
00:08:04,060 --> 00:08:06,720
So you notice here I put all of the yellow.

116
00:08:08,710 --> 00:08:12,010
Portions that were highlighted here before, so.

117
00:08:13,170 --> 00:08:16,320
All those who are putting them back to back here to see if we can find a pattern.

118
00:08:19,270 --> 00:08:27,580
So let's see if Toyota came minus one plus one due to the came with two plus two to two to the K minus

119
00:08:27,580 --> 00:08:30,520
three plus three and two to the K minus four plus four.

120
00:08:31,030 --> 00:08:36,160
So you know, these obviously you can probably see a pattern is very similar to what we talked about

121
00:08:36,160 --> 00:08:36,580
before.

122
00:08:36,580 --> 00:08:38,260
We have similar numbers here.

123
00:08:39,280 --> 00:08:42,890
They kind of correspond with which I which iteration we are at.

124
00:08:42,910 --> 00:08:49,270
You know, so this was kind of the first one and then the second one and the third one and the fourth

125
00:08:49,270 --> 00:08:49,520
one.

126
00:08:49,540 --> 00:08:58,960
So what we can actually say is the eighth term is going to be T of two to the K minus I plus I.

127
00:09:00,650 --> 00:09:07,220
Because it corresponds with the term, we're on the one to first term, second term, third or fourth

128
00:09:07,220 --> 00:09:07,460
term.

129
00:09:07,790 --> 00:09:14,720
So what we can say then is that those eyes match up with these numbers here and so they can be replaced

130
00:09:14,720 --> 00:09:15,110
with I.

131
00:09:18,800 --> 00:09:20,660
OK, so let's solve the rest.

132
00:09:20,990 --> 00:09:22,580
So here's our term.

133
00:09:23,090 --> 00:09:25,080
So we're going to do what we did before.

134
00:09:25,100 --> 00:09:32,090
Let's assume that the base case let's assume the base case T of one where the base case.

135
00:09:32,090 --> 00:09:38,180
So then what we can do is do the same thing we did before where we take what's inside of the parentheses

136
00:09:38,180 --> 00:09:41,690
of the T here and we set it equal to what's inside here, which is one.

137
00:09:41,690 --> 00:09:44,090
So we're doing to the case when I say equals one.

138
00:09:45,620 --> 00:09:54,140
And you notice that I've kind of like got this in terms of, I guess, basically what we want to do

139
00:09:54,140 --> 00:09:55,950
is find out what I is.

140
00:09:56,510 --> 00:09:59,660
So we can replace it in the equation.

141
00:10:01,290 --> 00:10:06,450
And then after that, we'll try and get back to having it in terms of end so we can actually settle

142
00:10:06,450 --> 00:10:10,470
for an answer just like we did in the previous lecture.

143
00:10:11,580 --> 00:10:15,930
So I'm doing that here, and there's actually a slightly easier way I noticed I did this and kind of

144
00:10:15,930 --> 00:10:16,230
like.

145
00:10:17,690 --> 00:10:21,920
You know, like an extra.

146
00:10:23,250 --> 00:10:24,720
Steps kind of way.

147
00:10:24,750 --> 00:10:31,170
I guess that's why we've put it like that, but when I really could have just looked at the fact, you

148
00:10:31,180 --> 00:10:35,340
know, you can look at like it being two to the zero.

149
00:10:35,850 --> 00:10:36,570
So.

150
00:10:37,620 --> 00:10:41,670
I'll explain that in a second, but basically what you also could have done here instead of this mess

151
00:10:41,790 --> 00:10:48,450
is just say, OK, well, we know that T of one is actually T of two to the zero.

152
00:10:50,070 --> 00:10:58,620
And then if we said two to the zero equal to two to the K minus I is basically saying K minus II equals

153
00:10:58,620 --> 00:10:59,250
zero.

154
00:10:59,730 --> 00:11:01,830
And then we could have arrived at the same result.

155
00:11:01,920 --> 00:11:03,990
And that's probably a simpler way to do it.

156
00:11:03,990 --> 00:11:10,290
But we can also do here is just follow the traditional rulers of exponents and such.

157
00:11:11,400 --> 00:11:12,060
And so.

158
00:11:13,860 --> 00:11:24,000
What you can say for this term can be simplified actually into something that has this subtraction up

159
00:11:24,000 --> 00:11:29,520
here in the exponent, you can actually say it's two to the K over two to the eye.

160
00:11:31,860 --> 00:11:38,700
So if you do that, then what you can do is you have two to the K over to to the right here.

161
00:11:38,710 --> 00:11:45,210
So what you can what we did to get to this step was we multiplied by two to the I to remove this denominator

162
00:11:45,450 --> 00:11:46,650
on this fraction here.

163
00:11:47,400 --> 00:11:51,120
And so we also have to multiply by two over here if we do that.

164
00:11:51,720 --> 00:11:53,190
So we got rid of this.

165
00:11:54,130 --> 00:12:00,640
And then we multiplied one times, anything is just that thing, so we ended up with after getting rid

166
00:12:00,640 --> 00:12:05,590
of this, we have two to the K equals two to the I over on this side.

167
00:12:06,790 --> 00:12:11,200
And then some were just tuned this something equals two to the something we can actually just say that

168
00:12:11,200 --> 00:12:12,340
K equals I.

169
00:12:12,940 --> 00:12:14,620
So this is another way to do that.

170
00:12:15,310 --> 00:12:17,200
But of course, you could have just done that.

171
00:12:17,200 --> 00:12:21,040
Two to the zero is equal to two to the K minus I.

172
00:12:21,040 --> 00:12:22,480
And then you could say that.

173
00:12:24,120 --> 00:12:29,730
You know, K minus II is equal to zero, and then you could have added I to both sides, and that would

174
00:12:29,730 --> 00:12:31,770
have made the same result k equals I.

175
00:12:32,070 --> 00:12:34,640
So same thing there that would probably be a better way to do it.

176
00:12:34,640 --> 00:12:35,670
So I want to point that out.

177
00:12:37,490 --> 00:12:44,720
So now we have this K equals I, so that's the same thing as saying I equals K, so now that we know

178
00:12:44,910 --> 00:12:50,180
equals K, we can actually substitute K for I in this I term to simplify it.

179
00:12:51,890 --> 00:12:58,130
So therefore, we replace it with Kay, so we actually end up just getting tee of two to the K minus

180
00:12:58,130 --> 00:12:59,510
K plus K.

181
00:13:00,910 --> 00:13:03,880
K minus K, something minus itself is zero.

182
00:13:04,300 --> 00:13:08,290
And so we get T of two to the zero plus K.

183
00:13:08,590 --> 00:13:08,950
Huh.

184
00:13:08,980 --> 00:13:09,850
Interesting.

185
00:13:09,880 --> 00:13:12,100
T of two to the zero.

186
00:13:13,130 --> 00:13:15,710
Well, what is that due to the zero?

187
00:13:16,700 --> 00:13:18,650
Well, that's one, right?

188
00:13:19,190 --> 00:13:23,420
So that's T of one, and we already know what Tier one is.

189
00:13:24,500 --> 00:13:26,660
So basically.

190
00:13:28,600 --> 00:13:35,230
What we can do is simplify this, so to to this zero is one.

191
00:13:35,260 --> 00:13:41,530
So we know that this is actually T of one and we know T of one equals one for our base case, if you

192
00:13:41,530 --> 00:13:42,160
recall that.

193
00:13:43,160 --> 00:13:49,400
At the same time, what we're going to do is recall that N equals two to the K.

194
00:13:51,060 --> 00:13:58,500
And we also want to recall the properties of logarithms that we discussed, this can actually be reorganized

195
00:13:58,500 --> 00:14:00,300
in terms of a logarithm.

196
00:14:00,300 --> 00:14:05,340
So if you remember back to what we talked about with large, see if you can actually maybe pause the

197
00:14:05,340 --> 00:14:09,630
video and turn this into an expression with a logarithm.

198
00:14:11,520 --> 00:14:19,140
OK, so what we would actually do is we can rearrange n equals two to the K to actually be K equals

199
00:14:19,140 --> 00:14:21,090
log base two of N.

200
00:14:22,190 --> 00:14:28,280
And then, like I said before, recall that T of two to the zero is actually T of one because two of

201
00:14:28,280 --> 00:14:29,240
the zero is one.

202
00:14:29,750 --> 00:14:33,440
So the same thing as saying T one, and we know that T of one equals one.

203
00:14:33,980 --> 00:14:38,150
Knowing all these things, we can actually change this expression right here.

204
00:14:40,970 --> 00:14:47,180
So if K goes a long way to heaven, we can substitute for K and if we know T of two, the zero is T

205
00:14:47,180 --> 00:14:51,500
of one and that T of one equals one, we can actually substitute that right here.

206
00:14:52,430 --> 00:15:00,020
And so what we end up with is we can say that we actually have something like T in so we can get this

207
00:15:00,020 --> 00:15:00,320
back.

208
00:15:00,320 --> 00:15:06,340
In terms of N, since we have this log base, two women equals one plus log base, two of RN.

209
00:15:07,160 --> 00:15:14,300
And our time complexity would then be theta log in because we can get rid of this constant and ignore

210
00:15:14,300 --> 00:15:15,170
the base to.

211
00:15:16,190 --> 00:15:22,100
And so that's fully simplified now, and we have solved it all the way to get tight bounds.

212
00:15:23,600 --> 00:15:25,460
OK, so hopefully that makes sense.

213
00:15:26,210 --> 00:15:32,210
This part, there was kind of a lot going on, but if you just kind of walk through it again, we just

214
00:15:32,210 --> 00:15:33,290
did some simple math.

215
00:15:33,560 --> 00:15:37,760
And once again, you remember I said, you could also just think of this as like two to the zero and

216
00:15:37,760 --> 00:15:38,600
have K minus.

217
00:15:38,600 --> 00:15:41,540
I set this equal to two to the zero.

218
00:15:41,870 --> 00:15:44,170
And then came on to side could be set equal to zero.

219
00:15:44,180 --> 00:15:45,500
Then you can end up with quite a side.

220
00:15:45,560 --> 00:15:47,300
So the easiest way to do that as well.

221
00:15:47,960 --> 00:15:54,170
And then this is just remembering these properties of the log and also the things that we said originally

222
00:15:54,170 --> 00:15:54,890
in the base case.

223
00:15:54,890 --> 00:16:06,230
So we basically got the I term simplified by trying to get IE equal to K get high in terms of K, that

224
00:16:06,230 --> 00:16:07,730
helped us simplify the term.

225
00:16:08,240 --> 00:16:14,450
And after that, we were able to use our knowledge of the base case and use our knowledge of logarithms

226
00:16:14,450 --> 00:16:17,210
to get this back into terms of MN.

227
00:16:17,780 --> 00:16:23,750
And then that led us to our time complexity after just looking for this term and getting rid of constants.

228
00:16:24,950 --> 00:16:25,410
OK.

229
00:16:25,700 --> 00:16:28,850
So after that recap, hopefully this multinational rule makes sense to you.

230
00:16:29,210 --> 00:16:38,450
It's really just useful when you have a floor division in the recurrent recursion part of the recurrence

231
00:16:38,450 --> 00:16:39,230
relation there.

232
00:16:40,160 --> 00:16:45,500
So I wanted to point that out because I think it's an important, important rule.

233
00:16:45,770 --> 00:16:51,920
And now that you've done this and that previous recurrence relation and kind of the basic recurrence

234
00:16:51,920 --> 00:16:55,700
relations, you should now have a decent idea of how to go through these things.

235
00:16:56,300 --> 00:16:56,570
All right.

236
00:16:56,570 --> 00:16:58,310
So with that, I will see you in the next lecture.