OK, so now that we have thoroughly reviewed our bounds and cases and gotten up to speed on that, it
is time for us to look at an actual more formal analysis of algorithms.
And the first thing we're going to look at as far as that is iterative algorithms.
And what I mean by iterative is like loops and such.
So let's get right into it.
So just recapping again and then looking at how we formally analyze an algorithm, we pretty much do
the same thing that we did when we first talked about it.
We're just interested in counting the basic operations, a number of basic operations that happen in
the algorithm.
So we choose a basic operation like multiplication or addition.
And we pick the basic operation that we think will probably happen the most times get executed the most
times.
The only difference is that this time math.
So we do need to use a little bit of math, haven't really exposed a whole lot of math so far in this
course, besides very basic things like arithmetic and all that.
But we are going to have to do a little bit of math.
So quick tangent and rant.
You do not need to be an absolute math prodigy and be obsessed with math and just love math and dream
about math.
And, you know, be the smartest person in the entire world who's just solving groundbreaking equations
and formulas.
No, you do not need that.
You do not need that to be a software engineer.
Many people will say that you just need to love math and don't even try.
Six.
If you're not just really good at math, you'll just fail miserably.
So I personally do not believe that any of that is true.
There's a lot of these jobs where you rarely have to do any math other than like arithmetic and stuff
like that.
Maybe very basic algebra.
And things like that, so you do not have to be a math genius to succeed in this subject and profession.
And I am not going to try and dump some heavy mathematics on you in this course.
Just try and expose you to as many tools and things that could help you as I can.
And so even though you might hear this a lot, I definitely just don't believe that that you need to
be some math genius to succeed in software engineering, programming, whatever you want to call it.
You know, the IT industry.
So there, of course, are some jobs in the STEM fields of computer science that heavily rely on mathematics.
But it's not something that you need to know for every single job.
In all areas of computer science, it is better to try and it is good to try and kind of get comfortable
with math because it definitely could help you.
You know, if something comes up where you need to know something.
Use some math to figure something out.
It could definitely help you.
And you know, a lot of the theory of computer science is based on some pretty important mathematical
concepts.
But I do not think that you need to be an absolute math genius to succeed.
So just want to put that out there.
So with that said, let's jump into some math.
So I'm just going to pretend that there's I have no idea who is watching this right now.
It could be someone who's never been exposed to any of these things I'm about to talk about, or some
people may have seen them in their school courses but forgot about them.
Or, you know, maybe you're comfortable with this and you are not needing to hear a lot of the things
that I'm going to say about these, but we're going to apply them to code.
So I would think it would be still a good idea to listen to it.
But if you have seen something like this and you already know what this is, then you may be able to
skip a slide or two.
So let's see what is this right here, so I'm just going to hint that there are some people that haven't
seen this before.
This is a summation.
This right here is the Greek alphabet letter Uppercase Sigma.
This down here is a lower limit, and this up here is an upper limit.
And this is the thing that we are talking about summing up.
So a sum is just us adding things up.
So one plus one plus one, the sum of one plus one plus one is three.
So we do know it's basically just adding things together, and this is the mathematical notation for
something like that.
So for example, if you were to expand this, this is what we call this right here and expansion of
it.
It would just be one plus one plus one, we're starting at one, so we start at one and then we're adding
the thing that we're assuming is once.
And we're going up to.
So start at one some.
The number one up to and so one plus one plus one plus one all the way up to in.
And so let's take an example right here.
Let's say we want the some of this and the unknown variable we put in here is four inches for a place
and with four.
So that would be starting at one anyone until you get to force one plus one plus one plus one.
So one two three four.
Tell in is for.
So will we be incrementing and I would be going up and so it would be, you know, one and two and then
three and then four, and then we're at a staffing condition, which is four.
And so the answer would be four because one plus one plus one plus one is four.
And so if we just put in and there is a variable, we know that our answer will be in because we're
just doing this pattern over and over again one plus one plus one plus one plus one all the way up to
end.
OK, so now we got those basics out of the way.
How would we use these submissions and why would we use them for code?
So here I have a for loop on the left.
So the sum is used to set up a way for us to formally analyze the time complexity of an algorithm here.
So right here, you notice that I say some of one operation, so that means some constant operation
is happening inside of this four loop right here.
So that is why we have the number one right here.
Let's look at the conditions of the loop.
So the loop starts at zero and so let's grab this part right here.
Starts is zero, so that is why we have I equals zero here because we have an equal zero here.
This is our starting condition than we have, I is less than 18, so when I is equal to in this for
loop will be taking that into account.
It will be like I is equal to N.
I said I less than in, so I'm not going to execute this in here because I is and it will not execute
anymore.
It will go past.
We know that from the code we've written so far, so we know that the last time this is going to get
executed.
Is when I is the same as one before in which is the same thing as saying I is equal to n minus one.
So we know that in minus one is our stopping condition then, so that is our upper limit here, so we
can say in minus one up here.
And what are we doing?
Well, we're counting the number of times that this gets executed, and so if this is representative
of just one thing.
And it's happening over and over and over again.
That leads us to use a summation.
So we're doing this some of this operation to try and figure out how many times they executes.
And so what we would do next is it's a little bit easier to calculate our thumb if we go back here.
You notice we started, I equals one and we went up to em.
And so if we just want to make it the same as this one, just for simplicity, we can do that just because
this is just a one over here.
So we can just bump this up by one and say, OK, let's start at one.
And then if we do that, so if we want it to run the same amount of times, we don't want to change
what this represents, the amount of times that it's happening.
So we also increase the upper limit by one.
And we can do that since we just have a constant over here.
So we are just going to say start it one up to end to simplify and make our lives easier instead of
going to zero to minus one.
So we can do the same type of thing that we did before.
And so like we saw before, this is just one plus one plus one plus one we're adding up.
This is basic basic operation, basic operation, basic operation all the way up to end, and we know
that the answer for this.
Is in and so let's related to the actual loot.
So we have I started at zero just to make you confident that us changing these lower and upper limit
didn't miss anything.
I zero, right?
Let's go through the loop.
So if I have zero, we execute this on ice zero.
So that's one.
I as one, we execute this again.
I so I just want we executed again, that's too so we can even just look at it right here, right?
This is the same as a basic operation.
So I zero, let's say this is the first basic operation.
I is one.
OK, now we do a basic operation again.
OK, now we go to the next one is two.
We go to this basic operation here.
I have three go to this basic, basic operation here, so let's go ahead and do think of that example.
So let's say that in was for like it.
Like some, we got user input.
Let's say it's dependent on that and the user interface for and we save that into the variable in and
then we do our loop right here.
So that would make us do what we just talked about here when I was zero, we do a basic operation.
When I is one, we do a basic operation, when I is to basic operation, when I is three, we do a basic
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
not going to execute this anymore.
We're done.
Well, that happened four times and we said in was equal to four.
And so our answer is equal to and so we just can say in.
So that happened in times.
So that was just like ultra basic example there to get us comfortable with this concept.
So let's step it up just a bit and let's actually look at coming up with an actual Bigo for our answer.
So I'm going to introduce this new sound first before I get into the code.
So instead of one, we have an eye here, so what would that do so if we think about the eye of our
eye loop?
Let's say it starts at one, let's just say we're going to start at one instead of zero, you know,
we could start to zero two, but it would just go up.
One at a time, you know, like that, let's say we're doing it plus plus like that.
So it's one and two and three and four, and the thing that we're adding is I.
So that would look something like this when we expand it.
So one plus two plus three plus four up till stopping condition in.
It just so happens that some great mathematicians came up with things called closed form formulas for
this.
So this is representative of this, some kind of a simplified version where we can actually just go
through this, the mathematics of this rather than having to expand this or look for other substitutions
or things like that.
So.
This is a closed form right here.
Let's see how it relates to this, so if I was to choose for again, like we were just talking about.
I said in is for.
So let's do that.
So if it is for, then we're going to stop at one to three four, we would stop right here.
So if we're summing up, I mean, we go up until in is for it would be one plus two plus three plus
four, which is three four five six seven eight nine 10.
So the sum of that is 10.
Let's do the same thing.
So we say in his for the top over to our closed form and see how this is the same thing.
So replace in with four.
Let's substitute for four in in this formula right here.
So four plus one is five, right?
And then let's substitute a four in this and two and we're going to multiply that since we just have
these parentheses right here, it's insinuated that we're distributing that in here.
So we already saw this.
This is five four plus one is five, four times five is 20 and twenty, divided by two is 10.
So same thing four or five six seven eight nine 10.
We calculated this is 10.
Close form is 10.
You can now see how they are related.
And this is a much faster, more simple way to kind of used to calculate these things.
You know, more faster math in quick math.
So let's see how this actually relates to our code.
And a quick note that I want to say real quick is that there are some great cheat sheets out there that
you can search up.
I didn't insert one here in the slideshow because I don't want to use copyrighted material on here,
some someone's cheat sheet that they made.
But you can search something like summation formula, cheat sheet, and you can find a great amount
of closed form formulas for all of these different summations that you may come up with for a year.
Iterative analyses.
So just want to throw that out there?
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
something like that for the course.
So what code would lead us to use that summation?
Well, we got something over here.
Let's check this out.
So we've got two nested.
We got one nested loop inside of another loop here.
And then in that inner loop, we have our basic operation, which is just some constant operation.
So here is the sum that we would set up for this, so let's look at why this would be the situation.
We're going to set this set up for this.
So let's check out the outer loop.
This right here is representative of the outer loop.
And this right here is a representative of the inner.
So the outer loop, it's the same thing that we've seen before.
It starts zero goes up to one less than.
So that's why we would have originally just start with equals zero near minus one.
But we did the same thing we did before to simplify it, and we just added one to each of these.
So we're going to end.
And then we have this loop inside here.
And we are pretty much doing something very similar, except we noticed that look at the condition here.
J starts at zero and then goes up to one less than I, so it basically is taken into consideration what
I is at a given point.
So that is why we are saying are stopping condition would be one less than I, but instead of Jake was
here, we did the same thing.
We added one here and one here to simplify it and then our basic operation.
It's just a constant.
So we're doing the same thing and putting that one here.
So what do we do now, how do we simplify this?
Well, let's think back to the first summation we saw.
So if I go way back here to this summation right here.
We noticed that when we had just a one here and we started at one and went up to end, we noticed their
answer was in which is the same as the upper limit here.
So we can actually just do the same thing for this one that we're on right now.
So our upper limit is I.
And since we're just doing one over and over again up until I we know the answer is actually just going
to be I.
So what we can do is end up replacing this whole thing with I so like this so we can simplify this whole
thing to this.
So this was the sum of this whole thing because this was representative of the inner loop.
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
right here.
Starting from one going up to end of I.
So what can we do now?
Well, you've actually seen something exactly the same as this before.
So if we go back to here, we noticed that this is the same thing as what we have right now.
And we know that this is the closed form.
So let's go ahead and use that closed form.
So now we have our closed form.
But what we did in that previous slide that I just went to is we kind of stopped there and then we said
like, Hey, what would it be if we substituted for here?
Oh, neat, that's cool.
Look how the closed form relates to the summation with the Sigma.
But what if we actually want to get our time complex?
So we talked about big oh right and theta and all this stuff.
So let's actually analyze the true tone complexity and come up with like a bounce for this.
So what we can say is that since this is just one operation here, we're pretty confident that it's
going to happen.
For this, you know, based on like these conditions that we have here, we can formally analyze this,
there's no like conditional statement around it, you know, saying that it's only going to execute
dependent on some other condition.
We know our conditions right here and it's pretty clear.
So we should be able to get a tight bout on this and we can just analyze, you know, the.
And kind of do a more exact analysis, but we can still just say big and just throw an upper bound to
be confident about this.
So let's just do a big show of this right here and start at this closed form and see if we can simplify
this.
So what would we do to arrive at an answer where we could use the big go?
Well, this can be simplified a little bit, right?
So we have an in here and we have it in here, we know that previously we distributed that foreign to
here.
And so we can do the same thing within.
So in multiplied into this, we distribute the into both here and here.
In times n is n squared and in times one is in.
So we can simplify this actually to n squared plus n over two.
But it's kind of hard to simplify this further, and so you're you might be wondering like, OK, well,
what do I do now?
Well, if you think back, what is it?
What is it that we really care when we're saying we care about when we say we're we're doing big of
something?
Well, we don't care about Constance, right?
So we can get rid of this lake right here, this too.
And then if we recall further, we only really care about the term of the highest magnitude.
So we have it in here.
That's great, but in squared is greater than.
And so really, all we care about is in squared.
So what we can say then, is that this is actually big go of n squared.
So it is safe for us to say that when we analyze this algorithm right here, we can say it is Bigo of
N squared.
So that is a full walkthrough of an area of formal analysis.
And of course, this, you know, this topic goes a lot deeper.
And I'm hoping for us to get into maybe some other ones.
I'm pretty sure we will.
But for now, I'm going to stop right here and just kind of let this soak in.
And then in the lecture, the next lecture, I will be getting into how do we analyze not only loops,
but what if we have recursion?
So that will be the next lecture?
And then after that, we might actually get into some more complex problems than kind of these, these
two that we went over where a little bit is simple.
And of course, go check out those closed form sheets for summations.
They're very helpful.
Most of the time, what you want to do is just look up some of those forms and you should be able to
simplify most of the common algorithms with those.
So with that, I will see you in the next lecture you.