1
00:00:00,690 --> 00:00:08,430
So now that we have had a solid introduction to algorithm analysis, it's time for us to expose ourselves

2
00:00:08,430 --> 00:00:11,400
to some other, more interesting problems.

3
00:00:11,970 --> 00:00:18,150
And in this particular lecture, one I'm going to be looking at is binary search algorithm.

4
00:00:18,150 --> 00:00:22,560
So if some of you have not heard of binary search, that is totally fine.

5
00:00:22,560 --> 00:00:28,500
I'm going to go over the algorithm both in theory and the code implementation, of course, before I

6
00:00:28,500 --> 00:00:30,090
get into the analysis part.

7
00:00:30,390 --> 00:00:35,760
If you had her have heard of binary search or even maybe used it, this will just be a recap for you.

8
00:00:35,760 --> 00:00:39,870
And if you like, you can skip ahead to the portion in which we do the analysis.

9
00:00:40,500 --> 00:00:43,740
And I'm going to also be looking at the recursive implementation of this.

10
00:00:44,070 --> 00:00:46,960
Some of you who have already done it might think, Well, this can be done.

11
00:00:47,430 --> 00:00:52,740
Why are we doing it recursively in the purpose of doing it recursively is because I want this to be

12
00:00:52,740 --> 00:00:57,300
kind of a slight Segway into a sub topic of occurrence relations.

13
00:00:57,300 --> 00:01:03,840
And I think it will help us as a little introduction for a new topic, but I want to introduce in that.

14
00:01:04,350 --> 00:01:06,360
So with that, let's go ahead and get started.

15
00:01:07,660 --> 00:01:12,610
So the binary search algorithm, basically, it's a very efficient method of searching for an element

16
00:01:12,610 --> 00:01:16,060
in a solid list of items stored in a subscript double container.

17
00:01:16,750 --> 00:01:18,430
So what do I mean by that?

18
00:01:18,460 --> 00:01:22,190
Well, basically it just needs to be a container that is index able.

19
00:01:22,300 --> 00:01:26,710
So you need to be able to access an element at a given position that you might want.

20
00:01:27,340 --> 00:01:30,040
So something like a vector or an array, etc..

21
00:01:30,950 --> 00:01:32,930
And notice, they also said sorted.

22
00:01:33,020 --> 00:01:36,840
So that is a prerequisite of the binary search algorithm.

23
00:01:36,860 --> 00:01:40,340
The container must have the items sorted already.

24
00:01:41,630 --> 00:01:47,270
So the idea is basically that we just decrease the size of our search space by half each iteration of

25
00:01:47,270 --> 00:01:49,460
us looking for the value interested in.

26
00:01:50,000 --> 00:01:54,800
This is something we call a decrease and conquer algorithm since we're decreasing the size of the problem

27
00:01:54,800 --> 00:01:55,250
space.

28
00:01:56,750 --> 00:01:58,550
So let's get into what that looks like.

29
00:01:58,820 --> 00:02:00,140
So let's visualize it.

30
00:02:01,310 --> 00:02:06,650
I'm just going to go over a very basic kind of vague introduction to this for a visualization.

31
00:02:06,650 --> 00:02:10,820
And then afterwards, I will explain things in more detail as I do another example.

32
00:02:11,480 --> 00:02:18,710
So here I'm just going to say we have an array and on the left at the very beginning, I have this little

33
00:02:18,710 --> 00:02:21,310
arrow here called low in the middle.

34
00:02:21,320 --> 00:02:23,540
I have this little green arrow called me.

35
00:02:23,600 --> 00:02:30,290
And on the right, I have this little blue arrow called high, so low and high start out at either end

36
00:02:30,290 --> 00:02:36,740
of the array from the very beginning, and the mid is always supposed to be in between those to the

37
00:02:36,740 --> 00:02:38,150
midpoint in between those two.

38
00:02:39,020 --> 00:02:41,810
And so what we're going to do is search for twenty nine.

39
00:02:42,650 --> 00:02:43,820
And so basically.

40
00:02:45,030 --> 00:02:51,780
If whatever Mitt is pointing to here is bigger than 29, we're going to say, OK, well, since this

41
00:02:51,780 --> 00:02:55,920
container is sorted, if what I'm looking for is an.

42
00:02:58,320 --> 00:03:03,140
Less so this thing here is bigger than I know that I only want to look over here, I don't care about

43
00:03:03,140 --> 00:03:04,280
any of this over here anymore.

44
00:03:05,030 --> 00:03:06,500
And also vice versa.

45
00:03:06,500 --> 00:03:09,560
So the thing here is smaller than twenty nine.

46
00:03:10,040 --> 00:03:13,580
That means that I don't care about this right here or any of this over here anymore.

47
00:03:13,580 --> 00:03:15,500
So I want to look only at this.

48
00:03:16,720 --> 00:03:21,520
And we're going to do that by moving these little low and highs around and adjusting the mid to being

49
00:03:21,520 --> 00:03:22,090
between them.

50
00:03:23,170 --> 00:03:28,180
So let's start for searching for twenty nine 14 is obviously not twenty nine.

51
00:03:29,050 --> 00:03:33,350
So what we're going to do is move the low over here because we don't care about any of this anymore

52
00:03:33,350 --> 00:03:34,750
and we only care about this sound.

53
00:03:34,750 --> 00:03:38,440
So we're going to put the low in the high here and put this in between.

54
00:03:39,370 --> 00:03:40,750
Now we look at forty one.

55
00:03:41,200 --> 00:03:44,740
Well, forty one is bigger than what we're looking for.

56
00:03:44,740 --> 00:03:46,060
We're looking for a twenty nine.

57
00:03:46,510 --> 00:03:48,550
So we're just taking a look to the left.

58
00:03:49,930 --> 00:03:54,340
We only have this to go off of because we already aren't looking at this anymore.

59
00:03:56,040 --> 00:04:01,080
So now we're just looking here at twenty nine, which is actually what we're looking for.

60
00:04:01,380 --> 00:04:05,090
And you notice that the low in the mid and the high are all at the same element.

61
00:04:05,100 --> 00:04:09,900
So since the mid is pointing at twenty nine, that means we found it and we are done.

62
00:04:10,590 --> 00:04:11,550
So pretty simple.

63
00:04:12,540 --> 00:04:15,420
Let's break it down more so we can understand how this is actually happening, though.

64
00:04:16,440 --> 00:04:23,100
So here I put the indices so lowest starting out at zero and high and starting out with the last index,

65
00:04:23,100 --> 00:04:23,790
which is six.

66
00:04:24,600 --> 00:04:32,460
So the way that we calculate our midpoint is actually by rounding down doing the floor of the low plus

67
00:04:32,460 --> 00:04:34,260
the high divided by two.

68
00:04:35,040 --> 00:04:35,800
So let's do that.

69
00:04:35,820 --> 00:04:37,410
What is low, though, is zero.

70
00:04:37,470 --> 00:04:41,430
High is six six plus zero is six six.

71
00:04:41,430 --> 00:04:44,700
Divided by two is three evenly, so there's no need for rounding it down.

72
00:04:45,480 --> 00:04:46,950
So that's where Ahmed is.

73
00:04:48,900 --> 00:04:53,580
So the next thing to do is see whether we need to check to the left or the right.

74
00:04:53,880 --> 00:04:55,890
So in this example, I'm looking for 30.

75
00:04:56,810 --> 00:05:07,550
Thirty is greater than 14, so that means that the array made is smaller than 30, so that means we

76
00:05:07,550 --> 00:05:14,650
don't care about the index three anymore or anything to the left of Index three since this associate.

77
00:05:14,660 --> 00:05:20,220
So we are going to look to the right the way that we reduce our problem size, our problem space.

78
00:05:20,850 --> 00:05:26,600
And for this example, is to move the low to one right from the middle.

79
00:05:27,500 --> 00:05:29,060
And the way that we do that is pretty simple.

80
00:05:29,060 --> 00:05:31,190
We just say low equals mid plus one.

81
00:05:31,910 --> 00:05:33,120
Mitt is pointing at three.

82
00:05:33,830 --> 00:05:36,830
So three plus one is four, and that's when we're going to move low.

83
00:05:39,470 --> 00:05:41,210
So now we have a low pointing at four.

84
00:05:41,510 --> 00:05:46,640
So we don't care about this or anything to the left since our container sorted and we know that 30 is

85
00:05:46,640 --> 00:05:53,120
greater than 14, we're only considered in Worcester just to the right of it into the end of the container.

86
00:05:55,250 --> 00:05:57,740
So now that we've done that, we have to reinstate Ahmed.

87
00:05:58,790 --> 00:06:03,320
So we are going to say that made it a little farsighted available to round it down.

88
00:06:04,010 --> 00:06:06,980
So we're going to do for as low plus high as six.

89
00:06:06,980 --> 00:06:07,790
That's 10 10.

90
00:06:07,790 --> 00:06:12,110
Divided by two is five evenly, so we can just move it there to five.

91
00:06:13,290 --> 00:06:21,420
So we're looking for 30, 30 is less than forty one, so that means Pyramid is bigger than 30.

92
00:06:22,470 --> 00:06:27,110
So in this case, we're going to do pretty much the exact opposite of what we did with Low.

93
00:06:27,120 --> 00:06:34,290
So when we were moving low, we moved it to one to the right of mid four moving high.

94
00:06:34,320 --> 00:06:36,270
We're going to move it one to the left of it.

95
00:06:37,880 --> 00:06:41,010
So now we're reducing our problem, the space to just this one element.

96
00:06:41,030 --> 00:06:44,350
So what we're going to do is move high from over here.

97
00:06:44,900 --> 00:06:50,450
So high is six, but made minus one is four.

98
00:06:50,480 --> 00:06:52,160
So we're going to move higher over here to four.

99
00:06:54,680 --> 00:06:56,750
All right, so long hair in the same element.

100
00:06:56,780 --> 00:06:59,210
Now we need to recalculate our men once again.

101
00:06:59,930 --> 00:07:05,510
So if we do four plus four divided by two or that's just four, so men and low and high are all going

102
00:07:05,510 --> 00:07:06,950
to be on the same element here.

103
00:07:08,220 --> 00:07:11,610
Because we've effectively reduced our problem space again by half.

104
00:07:12,990 --> 00:07:19,110
So now they're all pointing to the same element, let's look at men is mid 30, no, it's 29.

105
00:07:19,500 --> 00:07:24,840
So ideally, you would just stop here if you're just looking at this basically like, OK, well, we're

106
00:07:24,840 --> 00:07:25,080
done.

107
00:07:25,080 --> 00:07:29,160
It's not in the array, but the algorithm actually keeps going just a bit more.

108
00:07:29,160 --> 00:07:30,990
And you may be thinking, well, that's not good.

109
00:07:30,990 --> 00:07:34,360
It's just going to be doing checks that it shouldn't be doing.

110
00:07:34,380 --> 00:07:36,400
But let's see how it actually stops itself.

111
00:07:38,060 --> 00:07:44,010
So we're going to just keep going and we're going to say, well, if arraignment is smaller than 30,

112
00:07:44,010 --> 00:07:45,330
then let's look to the right.

113
00:07:45,690 --> 00:07:48,090
So it is 30 is greater than 29.

114
00:07:48,600 --> 00:07:54,540
So we do that same thing where we move low one to the right of mid, so low equals mid plus one.

115
00:07:54,550 --> 00:07:56,850
So that means that low is going to move to index five.

116
00:07:58,980 --> 00:08:00,780
So we move to index five.

117
00:08:01,770 --> 00:08:07,380
And what actually happens now is that in our algorithm, we have a little stopping condition where if

118
00:08:07,380 --> 00:08:10,680
lo ever crosses to the right of high, we stop immediately.

119
00:08:10,690 --> 00:08:17,490
So if low is greater than high, we will stop and then we will return a negative one to show that the

120
00:08:17,490 --> 00:08:18,900
number was not found.

121
00:08:20,130 --> 00:08:21,900
So what does this look like in code?

122
00:08:22,200 --> 00:08:23,190
Let's take a look at it.

123
00:08:24,440 --> 00:08:26,450
So here is our stopping condition.

124
00:08:26,930 --> 00:08:31,070
I said we're going to do a recursive algorithm, so we're stopping condition is going to be our base

125
00:08:31,070 --> 00:08:31,430
case.

126
00:08:32,860 --> 00:08:35,710
And it's going to be at the top here, just like base cases normally are.

127
00:08:36,610 --> 00:08:41,980
So we're saying if low is greater than high, then just return a negative one.

128
00:08:42,700 --> 00:08:44,140
So that's when the low and high cross.

129
00:08:45,420 --> 00:08:49,530
The next thing is we have this little local variable that gets clobbered each time, but it updates

130
00:08:49,530 --> 00:08:52,950
before this code down here, which gives us the middle.

131
00:08:54,250 --> 00:08:57,310
So we see the main is the current level plus high divided by two.

132
00:08:57,580 --> 00:08:59,050
So that's getting calculated.

133
00:09:00,090 --> 00:09:05,850
Then what we do down here is we're looking at the condition in which the middle number is greater than

134
00:09:05,850 --> 00:09:06,570
our number.

135
00:09:07,580 --> 00:09:11,360
So if the middle number is greater than our number, that means that our number is less and therefore

136
00:09:11,360 --> 00:09:13,490
we want to look to the left right.

137
00:09:13,850 --> 00:09:17,450
So what we're doing is we're recursively calling the algorithm again.

138
00:09:18,400 --> 00:09:22,580
Of course, passing our array, then we're passing the thing we're looking for.

139
00:09:22,610 --> 00:09:26,900
We don't want to move the low because the thing that we're curious about is to the left.

140
00:09:27,500 --> 00:09:34,670
And so what we're going to do is basically update Hi vaginosis, this last parameter over here to one

141
00:09:34,670 --> 00:09:35,480
less than mid.

142
00:09:35,990 --> 00:09:39,290
So that's us effectively reducing the problem space and looking on the left.

143
00:09:41,150 --> 00:09:48,140
Different condition is this elusive right here, so I'll say, if you know, the middle number is less

144
00:09:48,140 --> 00:09:51,470
than our number, so our number is greater than what Mitt is pointing at.

145
00:09:51,650 --> 00:09:53,380
In that case, we're going to want to move the low.

146
00:09:53,390 --> 00:09:56,720
So you see the low parameter is the second to last parameter here.

147
00:09:57,820 --> 00:10:03,940
So what we're effectively doing is recalling the function where Lo is going to be one more than mid.

148
00:10:04,720 --> 00:10:08,110
So we'll be looking to the right instead.

149
00:10:09,670 --> 00:10:12,610
Otherwise, that means that we found it.

150
00:10:12,700 --> 00:10:18,280
So it's not greater than or less than that means that it's equal to since we found it, we can just

151
00:10:18,280 --> 00:10:20,020
go ahead and return the number.

152
00:10:23,740 --> 00:10:28,030
So now let's move into how we would analyze the time complexity.

153
00:10:28,570 --> 00:10:33,310
So if we look back at this code, let's think of how we could set up a recurring solution for this.

154
00:10:34,480 --> 00:10:35,530
Well, what's happening here?

155
00:10:35,650 --> 00:10:41,110
The base case happens when the problem size is one, so in low is greater than high.

156
00:10:42,060 --> 00:10:48,960
That basically means that the problem size has been reduced down to one because there's only one element

157
00:10:49,230 --> 00:10:51,150
in the container at that point in time.

158
00:10:51,900 --> 00:10:55,770
That means, you know that they would be on the they would all be on that same element.

159
00:10:56,340 --> 00:10:58,440
And then lo gets moved one over.

160
00:10:58,440 --> 00:11:00,060
So when there's one, they're all in the same element.

161
00:11:00,060 --> 00:11:03,410
That means basically that we only have one element left that we're considering.

162
00:11:03,450 --> 00:11:07,590
So the problem size, the problem, space size has been reduced to one.

163
00:11:08,250 --> 00:11:15,240
So because of that, we will be using something like T of one we care about when the problem sizes is

164
00:11:15,270 --> 00:11:18,300
one, that's when we're going to have our base case.

165
00:11:19,290 --> 00:11:22,230
And you notice that there's also like a basic operation here.

166
00:11:22,860 --> 00:11:27,540
If we're considering comparisons, then we have a comparison right here.

167
00:11:27,930 --> 00:11:33,270
And we also have a comparison right here because we have this greater than and less than so we could

168
00:11:33,270 --> 00:11:36,060
measure for the number of comparisons here.

169
00:11:38,050 --> 00:11:43,720
And then we have our recursive call, and so this is one of two possible recursive calls, and this

170
00:11:43,720 --> 00:11:46,150
is another one of those two possible recursive calls.

171
00:11:49,710 --> 00:11:51,570
So how would we set this up?

172
00:11:51,870 --> 00:11:57,490
Well, you notice that these are the calls that reduce the problem space by half.

173
00:11:57,510 --> 00:12:04,920
We talked about that in the very first bit of the lecture, how this algorithm is a decrease in conquer

174
00:12:04,920 --> 00:12:11,010
and it effectively decreases the problem space by half every iteration or every function.

175
00:12:11,010 --> 00:12:12,300
Call the recursive call.

176
00:12:14,140 --> 00:12:20,320
So since we're decreasing it by half instead of us doing and minus one, we don't really have that.

177
00:12:20,320 --> 00:12:23,350
Our input is not in in the parameters right here.

178
00:12:23,800 --> 00:12:27,190
What's happening is that the problem space is the whole array.

179
00:12:27,730 --> 00:12:34,930
And when we have it each time, then we can effectively say that, ah, if we're representing the problem

180
00:12:34,930 --> 00:12:40,210
space as in so that's our size of the input, then it's going to be divided by two.

181
00:12:40,870 --> 00:12:44,940
So each time we recursively call what you're doing and divide it by two.

182
00:12:47,050 --> 00:12:50,530
So let's set up that recurrence relation, so what is the base case?

183
00:12:51,220 --> 00:12:57,370
Well, we said the base case basically occurs when the problem size is one.

184
00:12:58,570 --> 00:13:02,260
So we're going to say T of one equals one.

185
00:13:02,950 --> 00:13:06,840
And you may be wondering, OK, well, why are we using one like that basic operation?

186
00:13:06,860 --> 00:13:09,490
We said it was number of comparisons.

187
00:13:10,540 --> 00:13:18,520
And so in this example, I'm just going to consider that constant here, even though we don't have a

188
00:13:18,520 --> 00:13:19,210
comparison.

189
00:13:19,210 --> 00:13:23,530
Because if you remember when I talked about their current situation, I said that it would end up with

190
00:13:23,530 --> 00:13:30,640
the same complexity because in the end, we're just really kind of abstracting away all these constants.

191
00:13:31,810 --> 00:13:38,440
And so this will make my problem easier to solve, and it's totally fine to just put some type of constant

192
00:13:38,440 --> 00:13:42,460
for the base case because honestly, you could imagine that that's getting at it anyways.

193
00:13:42,460 --> 00:13:46,030
There is an operation there, even if it's not the same as our basic operation.

194
00:13:46,330 --> 00:13:48,700
That was something that I described before.

195
00:13:48,700 --> 00:13:51,670
There was no multiplication in the base case, so I just put zero.

196
00:13:52,330 --> 00:13:57,460
But it would have turned out similarly if I do take the base case into account and just added that one

197
00:13:57,460 --> 00:14:02,440
extra constant operation because it would have been abstracted away when we got our final complexity

198
00:14:02,740 --> 00:14:04,750
and used to theta or bigger notation.

199
00:14:05,410 --> 00:14:07,570
So I'm going to say tier one equals one for that.

200
00:14:08,230 --> 00:14:11,980
The recursive portion, we said that was going to be in divided by two.

201
00:14:12,280 --> 00:14:15,850
The recursive call is can be represented by two over two.

202
00:14:17,500 --> 00:14:20,050
And then one you can put plus some constant.

203
00:14:20,050 --> 00:14:21,520
And why are we going to do that?

204
00:14:21,880 --> 00:14:25,570
Well, yeah, we have multiple comparisons, right?

205
00:14:25,570 --> 00:14:30,640
So comparison, basic operation comparison, basic operation comparison appear.

206
00:14:31,060 --> 00:14:40,270
But if what we just said was that these constants get abstracted away anyways, so what we can do most

207
00:14:40,270 --> 00:14:47,050
of the time when we're doing recurrence, relations for the time complexity is we can just say plus

208
00:14:47,050 --> 00:14:50,270
some constant and some people just represent that as see.

209
00:14:52,000 --> 00:14:53,470
Or you can just put one.

210
00:14:54,100 --> 00:14:55,630
So I'm just going to put one.

211
00:14:55,930 --> 00:15:01,210
So you could just think of one as just like some constant amount of operations because you remember

212
00:15:01,210 --> 00:15:04,450
a constant time is just kind of a hard coded thing.

213
00:15:04,450 --> 00:15:10,930
So if we have five, you know, or 100, when it comes down to it, it's not really changing.

214
00:15:10,930 --> 00:15:13,120
So we can always think of it as of one.

215
00:15:13,750 --> 00:15:16,660
And so I'm just going to represent that by putting a one here.

216
00:15:18,110 --> 00:15:21,080
So now we have our recurrence relation.

217
00:15:22,570 --> 00:15:27,010
Doesn't look too complicated, except this is kind of new here, right, because before we were doing

218
00:15:27,010 --> 00:15:34,090
something like in minus one, and I think we've only gone over examples so far, I think I had maybe

219
00:15:34,090 --> 00:15:36,880
a worksheet that I have included.

220
00:15:37,180 --> 00:15:40,390
If you haven't seen that yet, it was just in my S-1 as well here.

221
00:15:40,780 --> 00:15:43,690
And so now we're going into something with this division.

222
00:15:43,690 --> 00:15:46,210
So let's see how that actually plays out.

223
00:15:46,750 --> 00:15:48,970
So let's solve it via substitution.

224
00:15:50,590 --> 00:15:54,310
So we're starting out, we have a base case here, and then we have our actual formula.

225
00:15:54,730 --> 00:15:56,830
This is supposed to have tfn over that.

226
00:15:56,830 --> 00:15:58,650
I'm sorry, doesn't have to give in.

227
00:15:58,660 --> 00:16:01,960
So just imagine there's two of an around this with parentheses.

228
00:16:04,540 --> 00:16:05,050
So.

229
00:16:06,130 --> 00:16:10,840
When we start off, just kind of how we were curious about it, minus one, we're actually going to

230
00:16:10,840 --> 00:16:13,690
look into T minus two right off the bat.

231
00:16:13,690 --> 00:16:17,370
So this is kind of our first little mini substitution thing we do.

232
00:16:17,380 --> 00:16:21,760
So we're going to substitute in over two into the main formula.

233
00:16:23,140 --> 00:16:28,420
So imagine, of course, this has the tea with the parentheses wrapped around this, I forgot to put

234
00:16:28,420 --> 00:16:29,020
that sorry.

235
00:16:29,410 --> 00:16:36,970
So what we would do is if we replace in by an hour or two, we actually get in over two over two plus

236
00:16:36,970 --> 00:16:37,330
one.

237
00:16:37,420 --> 00:16:42,620
And so in over a two and then another over two is the same thing as two and over four.

238
00:16:43,540 --> 00:16:45,940
So now we've figured out what to in over two is.

239
00:16:48,480 --> 00:16:55,650
So what we can do now is we can take what to give it over to us and we can substitute that into where

240
00:16:55,650 --> 00:16:59,130
we last left off, which is right here because we only start at the beginning.

241
00:16:59,760 --> 00:17:04,950
So we'll substitute one over two equals two in and we were four plus one.

242
00:17:05,430 --> 00:17:12,370
So we put that right here and there's this extra plus one there, so we can simplify this two tier of

243
00:17:12,720 --> 00:17:14,700
tier in over four plus two.

244
00:17:16,650 --> 00:17:19,890
So now let's look at this to you and our four.

245
00:17:19,890 --> 00:17:28,410
And so for that, so and over four, we can substitute in over for four in so and over four over two.

246
00:17:28,950 --> 00:17:31,290
It's the same thing as saying T and over eight.

247
00:17:31,590 --> 00:17:32,640
So that simplified.

248
00:17:33,960 --> 00:17:38,220
And we just had we substituted this in the original formula, because that's what this substitution

249
00:17:38,220 --> 00:17:38,980
phase does.

250
00:17:39,000 --> 00:17:39,710
That's what we do.

251
00:17:39,720 --> 00:17:41,580
We substitute this in the original formula.

252
00:17:43,160 --> 00:17:44,840
Now we know of in over for.

253
00:17:44,960 --> 00:17:50,570
So if we look where we last left off, which is right here, this next line up, we can substitute this

254
00:17:50,570 --> 00:17:56,960
tea in over for with this since we know the tea of in our for equals this over here.

255
00:17:57,140 --> 00:17:58,190
So let's do that.

256
00:17:59,610 --> 00:18:03,930
So we take this whole thing in and replace this right here with that.

257
00:18:04,530 --> 00:18:09,210
So that becomes tive in over eight plus one and then the plus two.

258
00:18:11,130 --> 00:18:14,160
That we left off with, so it's actually not here, sorry, it's right here.

259
00:18:14,190 --> 00:18:16,140
This was our simplified equation, so.

260
00:18:17,460 --> 00:18:20,860
We have this trend in over eight plus one.

261
00:18:20,880 --> 00:18:25,170
It's actually replacing this right here because that's where we last left off.

262
00:18:25,650 --> 00:18:29,670
So that is why we have this trend over eight plus one and then the plus two.

263
00:18:29,680 --> 00:18:32,490
So that simplifies the trend over eight plus three.

264
00:18:35,250 --> 00:18:37,090
So do you see a pattern yet?

265
00:18:37,110 --> 00:18:41,790
We've only gone through a few iterations, but there's not a whole lot going on here, so you might

266
00:18:41,790 --> 00:18:43,430
already be able to see a pattern.

267
00:18:43,440 --> 00:18:49,650
So I see a pattern and what I see is I see this increasing.

268
00:18:51,070 --> 00:18:54,010
And I see this increasing out here.

269
00:18:55,980 --> 00:19:04,440
So we we have our end right here, but we want to look at these changing numbers, changing constants

270
00:19:04,440 --> 00:19:08,640
over here, and how can I compare these two?

271
00:19:08,790 --> 00:19:12,810
Well, for any given iteration for AI that were on?

272
00:19:14,260 --> 00:19:19,180
And remember, what I'm trying to do with the pattern is find that I term some thinking about that iteration

273
00:19:19,180 --> 00:19:19,700
that I'm on.

274
00:19:19,720 --> 00:19:20,740
So what I would be?

275
00:19:21,890 --> 00:19:23,540
So here I is.

276
00:19:26,150 --> 00:19:28,280
One so.

277
00:19:30,330 --> 00:19:37,350
If we have is one and then we have so I'm looking at these simplified things over here, remember,

278
00:19:37,410 --> 00:19:38,160
I think back.

279
00:19:39,140 --> 00:19:44,000
When I was first introducing it, I had them in yellow so that you can imagine like the yellow, things

280
00:19:44,000 --> 00:19:44,750
would be right here.

281
00:19:44,990 --> 00:19:46,400
So these right here.

282
00:19:48,990 --> 00:19:56,310
We have the simplifications, so we have this right here and then this right here and then this right

283
00:19:56,310 --> 00:19:56,640
here.

284
00:19:57,120 --> 00:20:04,260
So yeah, this one in the beginning, then the next simplification phase was this right here for our

285
00:20:04,260 --> 00:20:07,350
main formula here and we're looking at all the trends, events, right?

286
00:20:07,680 --> 00:20:10,380
So here the team in here at the event, and here's Steven.

287
00:20:11,250 --> 00:20:12,930
So we're considering this.

288
00:20:13,500 --> 00:20:14,580
And to you in this year.

289
00:20:14,580 --> 00:20:17,520
So we're considering this simplified form over here and here it is here.

290
00:20:17,520 --> 00:20:18,460
So we're considering this.

291
00:20:18,460 --> 00:20:21,750
So look at those three, this one, this one and this one.

292
00:20:23,160 --> 00:20:29,490
And what I notice is that when I is one, we have the same thing as I over here.

293
00:20:29,490 --> 00:20:32,160
So is one and this is one over here.

294
00:20:33,170 --> 00:20:34,640
When I asked to.

295
00:20:35,900 --> 00:20:37,670
We have this over here, too.

296
00:20:37,880 --> 00:20:44,090
And then when I asked three, we have this three over here, so I'm matches up with that number, so

297
00:20:44,090 --> 00:20:45,440
that could pretty much be I.

298
00:20:46,400 --> 00:20:52,970
This under here, though, we start out with two and we're successively dividing by two.

299
00:20:54,290 --> 00:20:57,980
You can think that the division is like the opposite of multiplication.

300
00:20:59,320 --> 00:21:04,480
And so when I think about this, like repeated multiplication instead of division, that would basically

301
00:21:04,480 --> 00:21:11,860
be like a power, because if you keep, you know, if you do two times, two times two, that's basically

302
00:21:11,860 --> 00:21:15,010
two to three to two of the third power.

303
00:21:16,180 --> 00:21:22,840
So if you think about it that way of it being a power, then that pretty much matches up with I.

304
00:21:24,180 --> 00:21:28,800
Right, because two to the one is to.

305
00:21:30,860 --> 00:21:37,670
And then when I as to if we have two of the two, that's for four right here, and if we go down to

306
00:21:37,670 --> 00:21:39,710
this last kind of TV and example.

307
00:21:41,160 --> 00:21:43,430
Two to three is eight.

308
00:21:45,620 --> 00:21:50,090
And so if I say to Tether and then one and then two and then three.

309
00:21:51,590 --> 00:21:55,590
So I mean, one and then two and then three for these numbers here.

310
00:21:56,000 --> 00:21:59,610
They actually match up with with these and we said this was I.

311
00:21:59,630 --> 00:22:04,970
They also match up with the idea where I as I as one here than I used to, and then I have three.

312
00:22:06,360 --> 00:22:12,450
So I'm thinking that this down here can actually be represented with like successive powers of two.

313
00:22:12,480 --> 00:22:15,690
So two to the eye and we said this was eye over here.

314
00:22:16,530 --> 00:22:22,410
So I'm going to say is that we can represent this as humans to you in over two to the eye.

315
00:22:23,410 --> 00:22:29,380
So this is all like you can imagine, this is kind of in parentheses and over to to the eye, it's not

316
00:22:29,380 --> 00:22:35,070
in our tuned in today because this number down here is basically going to be raised to the power of

317
00:22:35,070 --> 00:22:36,130
the given iteration.

318
00:22:36,640 --> 00:22:38,700
And in this, we said, was the same as I saw.

319
00:22:38,700 --> 00:22:39,880
I'm just going to put it there.

320
00:22:40,540 --> 00:22:43,000
So this is what I'm going to choose from my term.

321
00:22:43,390 --> 00:22:49,750
And hopefully you were able to see a similar pattern or at least understood it after I related to all

322
00:22:49,750 --> 00:22:51,400
of these iterations we were looking at.

323
00:22:51,410 --> 00:22:54,580
So this one, this one and this one.

324
00:22:56,880 --> 00:23:04,170
OK, so let's move on, so now our next step is is to use the term with the base case, right?

325
00:23:05,130 --> 00:23:10,590
So we notice that we have our item here in our base case with Tier one equals one.

326
00:23:12,330 --> 00:23:22,380
So if I say this is the same as one, so what we do is we're going to assume our base case, right,

327
00:23:22,380 --> 00:23:26,090
if you remember that from the previous recurrence relation lecture.

328
00:23:27,830 --> 00:23:32,510
If I have one in between here, I'm just going to consider when the problem size this one, then I can

329
00:23:32,510 --> 00:23:36,230
basically set what's in between here equal to that.

330
00:23:37,040 --> 00:23:39,200
So in order to do that, I equals one.

331
00:23:42,850 --> 00:23:47,830
And so if I want to simplify this, what I could do because what I want to do now is get it in.

332
00:23:49,570 --> 00:23:55,480
Terms of I like I basically want to solve for I because I eventually want to be able to put this in

333
00:23:55,480 --> 00:23:56,320
terms of end.

334
00:23:56,980 --> 00:24:00,070
So I want to replace I with and I have it in here.

335
00:24:00,070 --> 00:24:06,130
So I'm basically trying to get by to be equal to something of RN so I can replace it.

336
00:24:06,550 --> 00:24:06,940
Right?

337
00:24:07,840 --> 00:24:13,360
So what I'm going to do is multiply both sides by two to the I to get rid of this denominator here because

338
00:24:13,360 --> 00:24:14,680
this is like a fraction.

339
00:24:14,890 --> 00:24:20,560
So since it's divided by two, that if I multiply it by two to the I, it'll isolate and it'll basically

340
00:24:20,560 --> 00:24:21,670
make this, I just end.

341
00:24:21,820 --> 00:24:23,680
But I have to do the same thing to both sides.

342
00:24:24,040 --> 00:24:24,670
If I do that.

343
00:24:25,650 --> 00:24:32,370
So if I multiply one by two, I one times, you know, something times one is just a cell, so I end

344
00:24:32,370 --> 00:24:33,900
up with an equals to the eye.

345
00:24:34,980 --> 00:24:36,290
And so this is interesting.

346
00:24:36,300 --> 00:24:45,150
What do we do now if we want to basically get AI to equal something within so we can replace AI within?

347
00:24:46,550 --> 00:24:48,730
How are we going to do that with this right here?

348
00:24:49,850 --> 00:24:53,000
Some of you might already understand what to do.

349
00:24:54,140 --> 00:25:00,470
With this right now, but I'm going to ask I'm not assuming that anyone has any particular math background

350
00:25:00,470 --> 00:25:03,350
for this, except maybe some very basic algebra.

351
00:25:05,090 --> 00:25:12,110
And so for that, I'm going to kind of introduce logarithms.

352
00:25:12,200 --> 00:25:17,870
So what we can actually do at this point right now is we can actually use an interesting property that

353
00:25:17,870 --> 00:25:20,150
has to do with exponents and logarithms.

354
00:25:20,810 --> 00:25:25,130
So like I said, just in case some of you aren't familiar with logarithms, I'm going to go on a quick

355
00:25:25,130 --> 00:25:29,360
tangent to bring everyone up to speed on what is in the logarithm and how are we going to use it right

356
00:25:29,360 --> 00:25:29,600
now?

357
00:25:32,360 --> 00:25:39,650
OK, so black films are basically the opposite of exponents.

358
00:25:39,950 --> 00:25:40,640
So.

359
00:25:42,190 --> 00:25:52,270
If you're saying three squared equals nine, that can basically be reversed by saying log base three

360
00:25:52,270 --> 00:25:54,340
of nine equals two.

361
00:25:55,310 --> 00:26:01,760
So when we have three squared equals, nine two is the power that three is being raised to, so it's

362
00:26:01,760 --> 00:26:02,720
the exponent.

363
00:26:03,620 --> 00:26:09,640
But in log base, three of nine equals two three is the base of the logarithm.

364
00:26:09,690 --> 00:26:16,970
And what we're really asking is the three raise to what power is nine.

365
00:26:17,120 --> 00:26:21,110
So it's pretty much the opposite of an exponent there.

366
00:26:21,560 --> 00:26:30,170
So you notice that what we do is that we actually move the three and the three squared equals nine down

367
00:26:30,170 --> 00:26:30,990
to the base.

368
00:26:31,070 --> 00:26:34,400
So it's basically a number that's being raised to the power that turns into the base.

369
00:26:35,480 --> 00:26:41,630
And then the nine is always said equals nine, that's the thing you're taking long makes three of.

370
00:26:42,440 --> 00:26:46,180
And then what you're looking for is the power.

371
00:26:46,190 --> 00:26:47,890
So it's asking what the power is.

372
00:26:47,900 --> 00:26:51,350
So a lot of base three of nine is equal to two.

373
00:26:52,690 --> 00:27:02,500
So since we have this relationship, we can use this property to actually go back to what we simplified

374
00:27:02,500 --> 00:27:05,560
to before, which was an equals two to the eye.

375
00:27:06,100 --> 00:27:12,910
And we can say that it's the same thing as saying I equals log base two of and you notice that we take

376
00:27:12,910 --> 00:27:15,940
the two and we make that our base.

377
00:27:16,690 --> 00:27:18,580
We take the eye.

378
00:27:18,580 --> 00:27:21,910
And that's the thing that we're actually looking for, which is the power.

379
00:27:22,420 --> 00:27:26,950
And then we take the PN, which is on the other side of the equals sign from the exponent.

380
00:27:27,130 --> 00:27:30,340
And that is the thing that we're taking log base two of.

381
00:27:31,120 --> 00:27:32,110
So we're doing the same.

382
00:27:32,110 --> 00:27:33,940
Rearranging is what I mentioned above.

383
00:27:34,240 --> 00:27:39,400
And it's nice because when it does, that relationship can get this in terms of I.

384
00:27:39,910 --> 00:27:46,090
And once we have this in terms of why we have, I equals one vs two, then now we can go back and we

385
00:27:46,090 --> 00:27:54,070
can substitute EI by replacing an N in there, putting an end for IE in our current format, which is

386
00:27:54,070 --> 00:27:55,240
what we wanted all along.

387
00:27:58,870 --> 00:28:00,700
So let's list the things that we know so far.

388
00:28:02,210 --> 00:28:11,090
So DeHaven equals this term, we have that, then we just found out that we can do I equals log base

389
00:28:11,090 --> 00:28:19,160
to in because we rearrange that and equals to die and we have our base case T of one equals one.

390
00:28:20,200 --> 00:28:24,670
And then we also know that we were setting in order to equal to one.

391
00:28:26,770 --> 00:28:27,700
For that base case.

392
00:28:28,930 --> 00:28:36,820
So with those in mind, we can basically say this right here, Tiven equals T to the one because we're

393
00:28:36,820 --> 00:28:41,350
coming from our eighth time right here and we we can replace this with one because we have this right

394
00:28:41,350 --> 00:28:45,780
here and then we can replace.

395
00:28:45,790 --> 00:28:47,860
We basically said I.

396
00:28:49,310 --> 00:28:54,260
Equals log base two to the end, so you notice that we were replacing this with one right here, so

397
00:28:54,260 --> 00:28:55,070
that's what this is.

398
00:28:55,070 --> 00:28:58,280
It's T of one instead of T over two I.

399
00:28:58,640 --> 00:29:03,860
And then plus I always said, Oh, I think we're a long ways to an end so we can basically say this

400
00:29:03,860 --> 00:29:04,280
right here.

401
00:29:05,090 --> 00:29:10,730
And we already know tier one is one, so we can replace this with one so we can simplify to this one

402
00:29:10,730 --> 00:29:12,020
plus long ways to event.

403
00:29:13,100 --> 00:29:16,010
And we also know that we can abstract away the constant one.

404
00:29:16,160 --> 00:29:19,730
And what we can also do is abstract, away this base to for our answer.

405
00:29:20,600 --> 00:29:24,710
So now what I'm going to do, just because I'm just going to say it's big because I'm going to do an

406
00:29:24,710 --> 00:29:25,300
upper bound.

407
00:29:25,310 --> 00:29:32,690
I'm just going to say that and we can say that the answer is big of log in after we abstracted those

408
00:29:32,690 --> 00:29:32,990
away.

409
00:29:34,830 --> 00:29:36,930
So hopefully that broke it down for you enough.

410
00:29:38,990 --> 00:29:44,570
You know, you could also do a tight balance for this and say data, but I just wanted to show that

411
00:29:44,570 --> 00:29:48,920
we can use tobacco and of course, in industry, you know, a lot of times you're going to be looking

412
00:29:48,920 --> 00:29:49,730
at upper bounds.

413
00:29:50,780 --> 00:29:53,500
And so they use PAYGO.

414
00:29:53,510 --> 00:29:54,470
So I said bingo.

415
00:29:55,430 --> 00:29:56,980
So this is a little bit different.

416
00:29:56,990 --> 00:29:58,520
We have this excessive division, might you?

417
00:29:58,520 --> 00:30:01,220
But you noticed that it wasn't that much more difficult.

418
00:30:01,910 --> 00:30:06,680
But this is going to be a good segue into our next topic, which is going to be looking at.

419
00:30:06,950 --> 00:30:13,790
It's nice that we have this success of division by two, but it also is kind of problematic way to solve

420
00:30:13,790 --> 00:30:16,370
the way we've been doing if we didn't have.

421
00:30:18,470 --> 00:30:20,570
That that successive division.

422
00:30:22,560 --> 00:30:26,680
So, you know, if it were slightly different, if it if it wasn't like a power of two.

423
00:30:26,700 --> 00:30:29,430
So we're going to look into that soon as well.

424
00:30:29,550 --> 00:30:31,830
So a few things that I want to know and recap on.

425
00:30:32,490 --> 00:30:36,690
So just remember, a binary search requires the container you're using to be pretty sorted.

426
00:30:37,710 --> 00:30:42,930
It also requires that you have an index of all containers, so you can't use something like a linked

427
00:30:42,930 --> 00:30:44,430
list where you cannot index.

428
00:30:44,430 --> 00:30:51,210
This particular element in that data structure cannot be a binary search on a linked list the way that

429
00:30:51,210 --> 00:30:51,660
it is.

430
00:30:52,710 --> 00:30:59,070
So we also recovered recursive implementation, but I wanted to mention that you can also do an iterative

431
00:30:59,070 --> 00:30:59,910
implementation.

432
00:30:59,920 --> 00:31:03,990
So I think I mentioned that before that some people might have already done this and they've done iterative

433
00:31:03,990 --> 00:31:06,330
implementations so that it's totally possible.

434
00:31:06,690 --> 00:31:09,510
And you could also solve the time complexity of that as well.

435
00:31:09,780 --> 00:31:13,320
It would actually be the same time complexity, of course, the same algorithm.

436
00:31:14,090 --> 00:31:17,040
The space might be different, but I'm not getting to that right now.

437
00:31:18,960 --> 00:31:21,420
So that's pretty much it for binary search.

438
00:31:21,600 --> 00:31:24,390
And with that, I will see you in the next lecture.