1
00:00:01,010 --> 00:00:07,280
OK, so now that we have thoroughly reviewed our bounds and cases and gotten up to speed on that, it

2
00:00:07,280 --> 00:00:11,220
is time for us to look at an actual more formal analysis of algorithms.

3
00:00:11,630 --> 00:00:15,800
And the first thing we're going to look at as far as that is iterative algorithms.

4
00:00:15,800 --> 00:00:19,490
And what I mean by iterative is like loops and such.

5
00:00:19,730 --> 00:00:21,710
So let's get right into it.

6
00:00:22,490 --> 00:00:27,890
So just recapping again and then looking at how we formally analyze an algorithm, we pretty much do

7
00:00:27,890 --> 00:00:30,350
the same thing that we did when we first talked about it.

8
00:00:30,590 --> 00:00:36,080
We're just interested in counting the basic operations, a number of basic operations that happen in

9
00:00:36,080 --> 00:00:36,770
the algorithm.

10
00:00:36,780 --> 00:00:41,080
So we choose a basic operation like multiplication or addition.

11
00:00:41,390 --> 00:00:47,330
And we pick the basic operation that we think will probably happen the most times get executed the most

12
00:00:47,330 --> 00:00:47,870
times.

13
00:00:48,230 --> 00:00:51,890
The only difference is that this time math.

14
00:00:52,250 --> 00:01:00,290
So we do need to use a little bit of math, haven't really exposed a whole lot of math so far in this

15
00:01:00,290 --> 00:01:04,520
course, besides very basic things like arithmetic and all that.

16
00:01:04,850 --> 00:01:07,010
But we are going to have to do a little bit of math.

17
00:01:08,120 --> 00:01:10,310
So quick tangent and rant.

18
00:01:10,970 --> 00:01:20,150
You do not need to be an absolute math prodigy and be obsessed with math and just love math and dream

19
00:01:20,150 --> 00:01:20,840
about math.

20
00:01:20,840 --> 00:01:27,980
And, you know, be the smartest person in the entire world who's just solving groundbreaking equations

21
00:01:27,980 --> 00:01:28,610
and formulas.

22
00:01:29,000 --> 00:01:30,350
No, you do not need that.

23
00:01:30,920 --> 00:01:32,960
You do not need that to be a software engineer.

24
00:01:33,380 --> 00:01:38,020
Many people will say that you just need to love math and don't even try.

25
00:01:38,030 --> 00:01:38,650
Six.

26
00:01:38,660 --> 00:01:43,370
If you're not just really good at math, you'll just fail miserably.

27
00:01:43,910 --> 00:01:48,350
So I personally do not believe that any of that is true.

28
00:01:49,610 --> 00:01:55,700
There's a lot of these jobs where you rarely have to do any math other than like arithmetic and stuff

29
00:01:55,700 --> 00:01:56,150
like that.

30
00:01:56,480 --> 00:01:58,610
Maybe very basic algebra.

31
00:01:59,640 --> 00:02:06,120
And things like that, so you do not have to be a math genius to succeed in this subject and profession.

32
00:02:06,450 --> 00:02:11,700
And I am not going to try and dump some heavy mathematics on you in this course.

33
00:02:12,150 --> 00:02:20,970
Just try and expose you to as many tools and things that could help you as I can.

34
00:02:21,330 --> 00:02:29,430
And so even though you might hear this a lot, I definitely just don't believe that that you need to

35
00:02:29,430 --> 00:02:36,420
be some math genius to succeed in software engineering, programming, whatever you want to call it.

36
00:02:36,450 --> 00:02:38,130
You know, the IT industry.

37
00:02:39,210 --> 00:02:47,820
So there, of course, are some jobs in the STEM fields of computer science that heavily rely on mathematics.

38
00:02:47,820 --> 00:02:51,030
But it's not something that you need to know for every single job.

39
00:02:51,030 --> 00:02:58,920
In all areas of computer science, it is better to try and it is good to try and kind of get comfortable

40
00:02:58,920 --> 00:03:01,380
with math because it definitely could help you.

41
00:03:01,950 --> 00:03:06,000
You know, if something comes up where you need to know something.

42
00:03:06,030 --> 00:03:08,190
Use some math to figure something out.

43
00:03:08,760 --> 00:03:10,140
It could definitely help you.

44
00:03:10,150 --> 00:03:16,380
And you know, a lot of the theory of computer science is based on some pretty important mathematical

45
00:03:16,380 --> 00:03:16,920
concepts.

46
00:03:16,920 --> 00:03:21,510
But I do not think that you need to be an absolute math genius to succeed.

47
00:03:21,540 --> 00:03:22,770
So just want to put that out there.

48
00:03:23,790 --> 00:03:27,990
So with that said, let's jump into some math.

49
00:03:28,440 --> 00:03:35,800
So I'm just going to pretend that there's I have no idea who is watching this right now.

50
00:03:35,820 --> 00:03:41,760
It could be someone who's never been exposed to any of these things I'm about to talk about, or some

51
00:03:41,760 --> 00:03:47,180
people may have seen them in their school courses but forgot about them.

52
00:03:48,240 --> 00:03:56,040
Or, you know, maybe you're comfortable with this and you are not needing to hear a lot of the things

53
00:03:56,040 --> 00:04:00,000
that I'm going to say about these, but we're going to apply them to code.

54
00:04:00,210 --> 00:04:04,530
So I would think it would be still a good idea to listen to it.

55
00:04:04,530 --> 00:04:11,190
But if you have seen something like this and you already know what this is, then you may be able to

56
00:04:11,190 --> 00:04:12,930
skip a slide or two.

57
00:04:14,520 --> 00:04:20,940
So let's see what is this right here, so I'm just going to hint that there are some people that haven't

58
00:04:20,940 --> 00:04:21,640
seen this before.

59
00:04:21,960 --> 00:04:23,790
This is a summation.

60
00:04:24,660 --> 00:04:30,090
This right here is the Greek alphabet letter Uppercase Sigma.

61
00:04:31,740 --> 00:04:36,810
This down here is a lower limit, and this up here is an upper limit.

62
00:04:36,810 --> 00:04:41,340
And this is the thing that we are talking about summing up.

63
00:04:41,760 --> 00:04:46,650
So a sum is just us adding things up.

64
00:04:47,230 --> 00:04:54,600
So one plus one plus one, the sum of one plus one plus one is three.

65
00:04:55,230 --> 00:05:04,350
So we do know it's basically just adding things together, and this is the mathematical notation for

66
00:05:04,350 --> 00:05:05,100
something like that.

67
00:05:05,130 --> 00:05:11,520
So for example, if you were to expand this, this is what we call this right here and expansion of

68
00:05:11,520 --> 00:05:11,670
it.

69
00:05:12,870 --> 00:05:18,990
It would just be one plus one plus one, we're starting at one, so we start at one and then we're adding

70
00:05:18,990 --> 00:05:20,820
the thing that we're assuming is once.

71
00:05:21,800 --> 00:05:23,210
And we're going up to.

72
00:05:24,080 --> 00:05:26,360
So start at one some.

73
00:05:27,590 --> 00:05:32,390
The number one up to and so one plus one plus one plus one all the way up to in.

74
00:05:34,720 --> 00:05:36,970
And so let's take an example right here.

75
00:05:37,090 --> 00:05:46,450
Let's say we want the some of this and the unknown variable we put in here is four inches for a place

76
00:05:46,450 --> 00:05:47,180
and with four.

77
00:05:47,200 --> 00:05:54,220
So that would be starting at one anyone until you get to force one plus one plus one plus one.

78
00:05:54,220 --> 00:05:56,590
So one two three four.

79
00:05:56,890 --> 00:05:58,450
Tell in is for.

80
00:06:00,280 --> 00:06:06,040
So will we be incrementing and I would be going up and so it would be, you know, one and two and then

81
00:06:06,040 --> 00:06:10,290
three and then four, and then we're at a staffing condition, which is four.

82
00:06:10,300 --> 00:06:14,800
And so the answer would be four because one plus one plus one plus one is four.

83
00:06:15,160 --> 00:06:21,820
And so if we just put in and there is a variable, we know that our answer will be in because we're

84
00:06:21,820 --> 00:06:27,070
just doing this pattern over and over again one plus one plus one plus one plus one all the way up to

85
00:06:27,070 --> 00:06:27,340
end.

86
00:06:28,540 --> 00:06:30,880
OK, so now we got those basics out of the way.

87
00:06:32,680 --> 00:06:37,570
How would we use these submissions and why would we use them for code?

88
00:06:37,600 --> 00:06:40,180
So here I have a for loop on the left.

89
00:06:41,910 --> 00:06:57,510
So the sum is used to set up a way for us to formally analyze the time complexity of an algorithm here.

90
00:06:58,700 --> 00:07:05,840
So right here, you notice that I say some of one operation, so that means some constant operation

91
00:07:05,840 --> 00:07:08,630
is happening inside of this four loop right here.

92
00:07:10,760 --> 00:07:13,250
So that is why we have the number one right here.

93
00:07:14,120 --> 00:07:16,910
Let's look at the conditions of the loop.

94
00:07:17,210 --> 00:07:23,460
So the loop starts at zero and so let's grab this part right here.

95
00:07:23,720 --> 00:07:29,510
Starts is zero, so that is why we have I equals zero here because we have an equal zero here.

96
00:07:30,640 --> 00:07:41,450
This is our starting condition than we have, I is less than 18, so when I is equal to in this for

97
00:07:41,470 --> 00:07:44,440
loop will be taking that into account.

98
00:07:44,440 --> 00:07:46,710
It will be like I is equal to N.

99
00:07:46,720 --> 00:07:52,900
I said I less than in, so I'm not going to execute this in here because I is and it will not execute

100
00:07:52,900 --> 00:07:53,350
anymore.

101
00:07:53,350 --> 00:07:53,970
It will go past.

102
00:07:54,220 --> 00:08:00,550
We know that from the code we've written so far, so we know that the last time this is going to get

103
00:08:00,550 --> 00:08:01,270
executed.

104
00:08:02,250 --> 00:08:10,920
Is when I is the same as one before in which is the same thing as saying I is equal to n minus one.

105
00:08:12,330 --> 00:08:19,380
So we know that in minus one is our stopping condition then, so that is our upper limit here, so we

106
00:08:19,380 --> 00:08:20,850
can say in minus one up here.

107
00:08:22,400 --> 00:08:23,420
And what are we doing?

108
00:08:23,420 --> 00:08:31,190
Well, we're counting the number of times that this gets executed, and so if this is representative

109
00:08:31,190 --> 00:08:33,500
of just one thing.

110
00:08:34,650 --> 00:08:36,900
And it's happening over and over and over again.

111
00:08:37,230 --> 00:08:40,290
That leads us to use a summation.

112
00:08:40,290 --> 00:08:46,260
So we're doing this some of this operation to try and figure out how many times they executes.

113
00:08:48,900 --> 00:08:58,650
And so what we would do next is it's a little bit easier to calculate our thumb if we go back here.

114
00:08:59,340 --> 00:09:02,760
You notice we started, I equals one and we went up to em.

115
00:09:03,480 --> 00:09:09,390
And so if we just want to make it the same as this one, just for simplicity, we can do that just because

116
00:09:09,390 --> 00:09:10,920
this is just a one over here.

117
00:09:12,480 --> 00:09:17,180
So we can just bump this up by one and say, OK, let's start at one.

118
00:09:17,190 --> 00:09:23,040
And then if we do that, so if we want it to run the same amount of times, we don't want to change

119
00:09:23,640 --> 00:09:26,630
what this represents, the amount of times that it's happening.

120
00:09:26,640 --> 00:09:29,040
So we also increase the upper limit by one.

121
00:09:30,330 --> 00:09:33,170
And we can do that since we just have a constant over here.

122
00:09:34,720 --> 00:09:41,110
So we are just going to say start it one up to end to simplify and make our lives easier instead of

123
00:09:41,110 --> 00:09:42,610
going to zero to minus one.

124
00:09:43,510 --> 00:09:46,240
So we can do the same type of thing that we did before.

125
00:09:47,110 --> 00:09:52,390
And so like we saw before, this is just one plus one plus one plus one we're adding up.

126
00:09:52,390 --> 00:09:59,170
This is basic basic operation, basic operation, basic operation all the way up to end, and we know

127
00:09:59,170 --> 00:10:00,580
that the answer for this.

128
00:10:02,060 --> 00:10:06,320
Is in and so let's related to the actual loot.

129
00:10:07,220 --> 00:10:13,790
So we have I started at zero just to make you confident that us changing these lower and upper limit

130
00:10:14,120 --> 00:10:14,900
didn't miss anything.

131
00:10:15,320 --> 00:10:16,370
I zero, right?

132
00:10:17,060 --> 00:10:18,090
Let's go through the loop.

133
00:10:18,110 --> 00:10:21,410
So if I have zero, we execute this on ice zero.

134
00:10:21,740 --> 00:10:22,700
So that's one.

135
00:10:23,730 --> 00:10:26,010
I as one, we execute this again.

136
00:10:27,620 --> 00:10:31,940
I so I just want we executed again, that's too so we can even just look at it right here, right?

137
00:10:32,330 --> 00:10:34,970
This is the same as a basic operation.

138
00:10:35,300 --> 00:10:39,500
So I zero, let's say this is the first basic operation.

139
00:10:39,890 --> 00:10:40,790
I is one.

140
00:10:41,090 --> 00:10:44,120
OK, now we do a basic operation again.

141
00:10:44,420 --> 00:10:47,420
OK, now we go to the next one is two.

142
00:10:48,200 --> 00:10:50,000
We go to this basic operation here.

143
00:10:51,860 --> 00:10:58,280
I have three go to this basic, basic operation here, so let's go ahead and do think of that example.

144
00:10:58,280 --> 00:11:03,740
So let's say that in was for like it.

145
00:11:03,740 --> 00:11:05,210
Like some, we got user input.

146
00:11:05,210 --> 00:11:11,510
Let's say it's dependent on that and the user interface for and we save that into the variable in and

147
00:11:11,510 --> 00:11:12,980
then we do our loop right here.

148
00:11:14,450 --> 00:11:19,070
So that would make us do what we just talked about here when I was zero, we do a basic operation.

149
00:11:19,070 --> 00:11:24,680
When I is one, we do a basic operation, when I is to basic operation, when I is three, we do a basic

150
00:11:24,680 --> 00:11:33,710
operation I has for Oh, I is four and is four I is equal to and we only said I listen in, so we're

151
00:11:33,710 --> 00:11:35,120
not going to execute this anymore.

152
00:11:35,180 --> 00:11:35,810
We're done.

153
00:11:36,200 --> 00:11:42,830
Well, that happened four times and we said in was equal to four.

154
00:11:43,490 --> 00:11:48,680
And so our answer is equal to and so we just can say in.

155
00:11:49,610 --> 00:11:51,470
So that happened in times.

156
00:11:52,890 --> 00:11:58,080
So that was just like ultra basic example there to get us comfortable with this concept.

157
00:11:59,130 --> 00:12:09,000
So let's step it up just a bit and let's actually look at coming up with an actual Bigo for our answer.

158
00:12:09,360 --> 00:12:13,670
So I'm going to introduce this new sound first before I get into the code.

159
00:12:15,350 --> 00:12:22,690
So instead of one, we have an eye here, so what would that do so if we think about the eye of our

160
00:12:22,690 --> 00:12:23,210
eye loop?

161
00:12:24,690 --> 00:12:30,870
Let's say it starts at one, let's just say we're going to start at one instead of zero, you know,

162
00:12:30,870 --> 00:12:34,050
we could start to zero two, but it would just go up.

163
00:12:35,290 --> 00:12:38,530
One at a time, you know, like that, let's say we're doing it plus plus like that.

164
00:12:39,920 --> 00:12:43,680
So it's one and two and three and four, and the thing that we're adding is I.

165
00:12:43,700 --> 00:12:46,190
So that would look something like this when we expand it.

166
00:12:46,670 --> 00:12:51,950
So one plus two plus three plus four up till stopping condition in.

167
00:12:53,130 --> 00:12:59,610
It just so happens that some great mathematicians came up with things called closed form formulas for

168
00:12:59,610 --> 00:12:59,880
this.

169
00:12:59,890 --> 00:13:07,530
So this is representative of this, some kind of a simplified version where we can actually just go

170
00:13:07,530 --> 00:13:12,210
through this, the mathematics of this rather than having to expand this or look for other substitutions

171
00:13:12,210 --> 00:13:13,110
or things like that.

172
00:13:14,040 --> 00:13:14,490
So.

173
00:13:15,670 --> 00:13:17,360
This is a closed form right here.

174
00:13:17,380 --> 00:13:23,350
Let's see how it relates to this, so if I was to choose for again, like we were just talking about.

175
00:13:24,530 --> 00:13:26,120
I said in is for.

176
00:13:27,490 --> 00:13:28,750
So let's do that.

177
00:13:29,950 --> 00:13:36,490
So if it is for, then we're going to stop at one to three four, we would stop right here.

178
00:13:37,270 --> 00:13:43,330
So if we're summing up, I mean, we go up until in is for it would be one plus two plus three plus

179
00:13:43,330 --> 00:13:47,950
four, which is three four five six seven eight nine 10.

180
00:13:48,820 --> 00:13:50,560
So the sum of that is 10.

181
00:13:50,860 --> 00:13:51,730
Let's do the same thing.

182
00:13:51,730 --> 00:13:56,650
So we say in his for the top over to our closed form and see how this is the same thing.

183
00:13:57,190 --> 00:13:59,050
So replace in with four.

184
00:13:59,050 --> 00:14:04,690
Let's substitute for four in in this formula right here.

185
00:14:05,290 --> 00:14:08,110
So four plus one is five, right?

186
00:14:08,110 --> 00:14:14,200
And then let's substitute a four in this and two and we're going to multiply that since we just have

187
00:14:14,200 --> 00:14:18,190
these parentheses right here, it's insinuated that we're distributing that in here.

188
00:14:18,640 --> 00:14:19,840
So we already saw this.

189
00:14:19,840 --> 00:14:27,820
This is five four plus one is five, four times five is 20 and twenty, divided by two is 10.

190
00:14:27,880 --> 00:14:30,580
So same thing four or five six seven eight nine 10.

191
00:14:31,660 --> 00:14:33,160
We calculated this is 10.

192
00:14:33,160 --> 00:14:34,230
Close form is 10.

193
00:14:34,240 --> 00:14:36,640
You can now see how they are related.

194
00:14:36,850 --> 00:14:43,600
And this is a much faster, more simple way to kind of used to calculate these things.

195
00:14:43,930 --> 00:14:46,870
You know, more faster math in quick math.

196
00:14:46,960 --> 00:14:50,950
So let's see how this actually relates to our code.

197
00:14:51,520 --> 00:14:56,380
And a quick note that I want to say real quick is that there are some great cheat sheets out there that

198
00:14:56,380 --> 00:14:57,130
you can search up.

199
00:14:57,400 --> 00:15:01,910
I didn't insert one here in the slideshow because I don't want to use copyrighted material on here,

200
00:15:01,930 --> 00:15:03,520
some someone's cheat sheet that they made.

201
00:15:04,540 --> 00:15:09,460
But you can search something like summation formula, cheat sheet, and you can find a great amount

202
00:15:09,460 --> 00:15:14,400
of closed form formulas for all of these different summations that you may come up with for a year.

203
00:15:14,410 --> 00:15:16,060
Iterative analyses.

204
00:15:16,750 --> 00:15:18,310
So just want to throw that out there?

205
00:15:18,550 --> 00:15:25,000
I might include one as a link if I can find a decent one and uh, yeah, so I might see if I can find

206
00:15:25,000 --> 00:15:26,050
something like that for the course.

207
00:15:27,160 --> 00:15:29,660
So what code would lead us to use that summation?

208
00:15:29,700 --> 00:15:32,020
Well, we got something over here.

209
00:15:32,320 --> 00:15:34,120
Let's check this out.

210
00:15:34,780 --> 00:15:36,820
So we've got two nested.

211
00:15:37,390 --> 00:15:40,090
We got one nested loop inside of another loop here.

212
00:15:40,960 --> 00:15:46,720
And then in that inner loop, we have our basic operation, which is just some constant operation.

213
00:15:49,020 --> 00:15:55,260
So here is the sum that we would set up for this, so let's look at why this would be the situation.

214
00:15:55,260 --> 00:15:57,270
We're going to set this set up for this.

215
00:15:57,540 --> 00:16:00,000
So let's check out the outer loop.

216
00:16:00,690 --> 00:16:04,490
This right here is representative of the outer loop.

217
00:16:04,500 --> 00:16:07,770
And this right here is a representative of the inner.

218
00:16:08,670 --> 00:16:11,400
So the outer loop, it's the same thing that we've seen before.

219
00:16:11,400 --> 00:16:13,960
It starts zero goes up to one less than.

220
00:16:14,790 --> 00:16:19,950
So that's why we would have originally just start with equals zero near minus one.

221
00:16:19,950 --> 00:16:24,600
But we did the same thing we did before to simplify it, and we just added one to each of these.

222
00:16:24,600 --> 00:16:25,680
So we're going to end.

223
00:16:27,380 --> 00:16:29,360
And then we have this loop inside here.

224
00:16:30,830 --> 00:16:38,930
And we are pretty much doing something very similar, except we noticed that look at the condition here.

225
00:16:39,500 --> 00:16:48,750
J starts at zero and then goes up to one less than I, so it basically is taken into consideration what

226
00:16:48,750 --> 00:16:50,150
I is at a given point.

227
00:16:51,420 --> 00:16:58,440
So that is why we are saying are stopping condition would be one less than I, but instead of Jake was

228
00:16:58,440 --> 00:16:59,340
here, we did the same thing.

229
00:16:59,340 --> 00:17:03,620
We added one here and one here to simplify it and then our basic operation.

230
00:17:03,630 --> 00:17:04,740
It's just a constant.

231
00:17:04,740 --> 00:17:06,990
So we're doing the same thing and putting that one here.

232
00:17:08,470 --> 00:17:11,200
So what do we do now, how do we simplify this?

233
00:17:12,960 --> 00:17:17,020
Well, let's think back to the first summation we saw.

234
00:17:17,040 --> 00:17:22,590
So if I go way back here to this summation right here.

235
00:17:24,050 --> 00:17:32,060
We noticed that when we had just a one here and we started at one and went up to end, we noticed their

236
00:17:32,060 --> 00:17:37,460
answer was in which is the same as the upper limit here.

237
00:17:38,270 --> 00:17:43,480
So we can actually just do the same thing for this one that we're on right now.

238
00:17:43,490 --> 00:17:45,620
So our upper limit is I.

239
00:17:46,640 --> 00:17:53,480
And since we're just doing one over and over again up until I we know the answer is actually just going

240
00:17:53,480 --> 00:17:54,230
to be I.

241
00:17:55,070 --> 00:18:02,000
So what we can do is end up replacing this whole thing with I so like this so we can simplify this whole

242
00:18:02,000 --> 00:18:02,840
thing to this.

243
00:18:02,840 --> 00:18:09,110
So this was the sum of this whole thing because this was representative of the inner loop.

244
00:18:09,480 --> 00:18:14,450
But now we're able to simplify this to ice so we can just say the sum of I, and that's what we put

245
00:18:14,450 --> 00:18:14,960
right here.

246
00:18:16,940 --> 00:18:18,980
Starting from one going up to end of I.

247
00:18:21,460 --> 00:18:23,770
So what can we do now?

248
00:18:24,340 --> 00:18:29,530
Well, you've actually seen something exactly the same as this before.

249
00:18:30,100 --> 00:18:36,190
So if we go back to here, we noticed that this is the same thing as what we have right now.

250
00:18:36,610 --> 00:18:38,650
And we know that this is the closed form.

251
00:18:39,250 --> 00:18:41,680
So let's go ahead and use that closed form.

252
00:18:42,670 --> 00:18:44,350
So now we have our closed form.

253
00:18:45,010 --> 00:18:50,350
But what we did in that previous slide that I just went to is we kind of stopped there and then we said

254
00:18:50,350 --> 00:18:52,960
like, Hey, what would it be if we substituted for here?

255
00:18:52,970 --> 00:18:54,100
Oh, neat, that's cool.

256
00:18:54,100 --> 00:18:57,550
Look how the closed form relates to the summation with the Sigma.

257
00:18:58,540 --> 00:19:00,670
But what if we actually want to get our time complex?

258
00:19:00,670 --> 00:19:03,850
So we talked about big oh right and theta and all this stuff.

259
00:19:05,160 --> 00:19:11,490
So let's actually analyze the true tone complexity and come up with like a bounce for this.

260
00:19:12,240 --> 00:19:20,790
So what we can say is that since this is just one operation here, we're pretty confident that it's

261
00:19:20,790 --> 00:19:21,870
going to happen.

262
00:19:22,890 --> 00:19:28,400
For this, you know, based on like these conditions that we have here, we can formally analyze this,

263
00:19:28,410 --> 00:19:34,290
there's no like conditional statement around it, you know, saying that it's only going to execute

264
00:19:34,290 --> 00:19:35,940
dependent on some other condition.

265
00:19:35,940 --> 00:19:38,370
We know our conditions right here and it's pretty clear.

266
00:19:39,380 --> 00:19:46,400
So we should be able to get a tight bout on this and we can just analyze, you know, the.

267
00:19:47,360 --> 00:19:53,990
And kind of do a more exact analysis, but we can still just say big and just throw an upper bound to

268
00:19:53,990 --> 00:19:55,130
be confident about this.

269
00:19:55,130 --> 00:20:02,690
So let's just do a big show of this right here and start at this closed form and see if we can simplify

270
00:20:02,690 --> 00:20:02,870
this.

271
00:20:02,880 --> 00:20:07,640
So what would we do to arrive at an answer where we could use the big go?

272
00:20:08,810 --> 00:20:11,900
Well, this can be simplified a little bit, right?

273
00:20:12,260 --> 00:20:17,450
So we have an in here and we have it in here, we know that previously we distributed that foreign to

274
00:20:17,450 --> 00:20:17,810
here.

275
00:20:18,530 --> 00:20:20,390
And so we can do the same thing within.

276
00:20:20,570 --> 00:20:24,890
So in multiplied into this, we distribute the into both here and here.

277
00:20:25,310 --> 00:20:30,550
In times n is n squared and in times one is in.

278
00:20:31,130 --> 00:20:35,960
So we can simplify this actually to n squared plus n over two.

279
00:20:38,070 --> 00:20:42,570
But it's kind of hard to simplify this further, and so you're you might be wondering like, OK, well,

280
00:20:42,570 --> 00:20:43,530
what do I do now?

281
00:20:43,770 --> 00:20:45,770
Well, if you think back, what is it?

282
00:20:45,810 --> 00:20:51,030
What is it that we really care when we're saying we care about when we say we're we're doing big of

283
00:20:51,040 --> 00:20:51,480
something?

284
00:20:52,230 --> 00:20:54,180
Well, we don't care about Constance, right?

285
00:20:54,180 --> 00:20:56,880
So we can get rid of this lake right here, this too.

286
00:20:57,600 --> 00:21:03,810
And then if we recall further, we only really care about the term of the highest magnitude.

287
00:21:04,470 --> 00:21:05,700
So we have it in here.

288
00:21:05,700 --> 00:21:08,260
That's great, but in squared is greater than.

289
00:21:08,280 --> 00:21:11,160
And so really, all we care about is in squared.

290
00:21:11,970 --> 00:21:17,550
So what we can say then, is that this is actually big go of n squared.

291
00:21:19,300 --> 00:21:26,610
So it is safe for us to say that when we analyze this algorithm right here, we can say it is Bigo of

292
00:21:26,650 --> 00:21:27,280
N squared.

293
00:21:28,720 --> 00:21:34,420
So that is a full walkthrough of an area of formal analysis.

294
00:21:34,430 --> 00:21:37,600
And of course, this, you know, this topic goes a lot deeper.

295
00:21:37,810 --> 00:21:41,230
And I'm hoping for us to get into maybe some other ones.

296
00:21:41,230 --> 00:21:43,090
I'm pretty sure we will.

297
00:21:43,600 --> 00:21:48,190
But for now, I'm going to stop right here and just kind of let this soak in.

298
00:21:48,190 --> 00:21:55,630
And then in the lecture, the next lecture, I will be getting into how do we analyze not only loops,

299
00:21:55,630 --> 00:21:57,160
but what if we have recursion?

300
00:21:57,520 --> 00:21:59,470
So that will be the next lecture?

301
00:21:59,470 --> 00:22:07,510
And then after that, we might actually get into some more complex problems than kind of these, these

302
00:22:07,510 --> 00:22:09,310
two that we went over where a little bit is simple.

303
00:22:09,910 --> 00:22:14,020
And of course, go check out those closed form sheets for summations.

304
00:22:14,890 --> 00:22:15,790
They're very helpful.

305
00:22:16,090 --> 00:22:21,190
Most of the time, what you want to do is just look up some of those forms and you should be able to

306
00:22:21,190 --> 00:22:25,510
simplify most of the common algorithms with those.

307
00:22:25,900 --> 00:22:28,720
So with that, I will see you in the next lecture you.