OK.
Welcome to the second part of this course where we will be looking at data structures and algorithms,
and we will be implementing these in C++, but there is also a theoretical component to this part of
the course.
And one of those theoretical components that we are going to start out with is going to be the efficiency
of our algorithms and data structures.
So of course, in this modern world, we care about how fast things run and how much space we can save.
And so we're going to look into those two things.
But first, we're going to look into time complexity, which is the runtime efficiency of a program
also referred to as Big O an industry.
So let's go ahead and get started.
So we're going to just do a really basic overview of this, and the point is just to have a metric so
we can properly evaluate the performance of our algorithms and data structures.
And so are just going to gloss over some terms here.
If you have some academic background in runtime efficiency and time complexity calculation and proving
it and all of that, you might be thinking there's a lot more to this.
It's not just bingo.
There are terms like Big Omega and Theta and things like that.
We all get into that later in the course where we look at more formal methods of evaluating this stuff
with summations and recurrent formulas.
But right now, we're just kind of going over it enough so we can start thinking about these things
when we're writing code for our algorithms and coming up with strategies for our algorithms and data
structures.
OK, so let's get started.
So what does it really mean?
Well, it's how fast or slow a specific piece of code or algorithm is.
And if you look at this chart down here, we can see that there's a few different graphs on here that
have varying degrees of steepness and shape.
So on the x axis, we have our elements and on the y axis we have operations.
And what's happening is what we want to consider.
Is the how are algorithm's performance changes?
As we have an increased amount of input coming in, so we're going to refer to the input size as in.
And then we care about as that increases here, how does the number of operations increase?
So how much work is it having to do?
So as we increase, that is the what is the rate of change, you know, if it becoming steeper, like
how quickly does it become steeper?
And we can see a different price difference between these lines.
We have some linear ones down here that are in this green zone and we would consider those down here
better time complexities than these ones up here in this red zone.
And you can see Big O event, we know of one of log in and log in, we're going to get into the specifics
of those later on.
We're going to go over some simple examples today just so you get the overall idea of it.
So for a first example, we're going to go ahead and look over at this piece of code over here, so
it's just a simple for loop.
And we have it starting in zero and going up until one less than in, so be in minus one.
So since we're starting zero and it will run on the 0th time, we know that there is going to this is
going to run for in times.
What we want to do is choose a basic operation and here we have three to choose from.
You're probably wondering, OK, how what one should I choose?
How do I know?
Of course, operations are different, but right now we're going to ignore that and we're just going
to pick one and I'm going to go ahead and pick multiplication.
So since this rise in times, we can see that this multiplication here is going to happen in times as
well.
And in fact, yeah, for every time this runs, we will also run this operation once every time, every
iteration of the loop.
So if we look over here two graphs, that is the explanation for why it is this and linear graph.
And I know this is kind of a shabby graph.
Just bear with me.
I just kind of threw together some graphs just enough to explain the point of these things.
But this line is our big go of in, and we say that because it happens in times and as we can see.
As our input is increasing at a certain rate, it is the same for our number of operations.
And that leads that is what leads us to call this linear time.
OK, so one simple example out of the way, let's move on to the next one.
So, Constantine, for this, we're looking at this code right here, and we noticed that there isn't
even really a for loop here.
And so we'll say, OK, let's do what we did before.
Let's choose a basic operation.
Let's go ahead and look at Edition.
When you say, well, there's three additions.
Hmm, I guess I'll just say bingo of three.
And that is a correct way of thinking.
But what we do for something we consider cost and time is we just simplify it to one.
And that is whenever we have some constant in here that we see, no matter how big it is, we're just
going to bring it down to one.
And the reason is is because if we look at this line over here and we think about what it means to have
some cost and time operation as our input changes increases what I should say, we don't really see
a change in how it affects this piece of code here.
Basically, you could put as many of these editions as you wanted, and all we would really do is raise
this horizontal line up.
But the fact is is it would still be a horizontal line.
And what we care about is the line itself and how steep it gets.
We're looking for that change, you know, as we add the input.
And something that's really important in comparing cost and time to the linear time we saw before is
thinking that if we go back here and we take this line and we put it on this graph, even if I was to
bring this oh of one line way up, let's say that we had one plus two plus three plus four all the way
up to five hundred and I brought this line way up or even a million at some point that oh of in line
is going to cross this of one line.
And that is important because that is what we can look at to help us understand why would Constantine
be better than linear time?
If I go back here, we see there is an oh of one and it's way down here and that is better than our
linear time, which is in the yellow zone here.
And that is the reason I want to point out.
It's because at some point that oh of in line would cross this cost and time line.
So let's look at another example.
This is another linear example.
But why?
Let's take a deeper look into it.
So we have another for loop and this for loop is going for the same amount of times that previous for
a loop that we looked at.
It's there starts to zero, goes up to one less than in.
And we just have this one statement in here that we want to execute.
We have a similar for loop down here, but it just goes backwards.
It's decreasing and it starts to end and goes down to zero.
So if we looked at this intuitively, we might say, OK, well in times here and in times here, and
we do in plus in.
So in-person would be two in, and that is correct in thinking that, but what we're going to do is
actually generalize that more interrupt this constant and just call it O event.
And you see, as we go on, this is kind of the way we do things.
We think, Oh, we're really only interested actually in the largest term.
So if we were to have like more things in here, Constance, and you know, you have some kind of polynomial.
No, I wouldn't.
I would just say, actually, you have some kind of expression in here and then we would just have like
two men plus two or something like that.
It would still just be in.
So that's why we're getting rid of that constant, and you'll notice that we continue to do that even
with more complex examples.
So let's look at a more complex example, and for this one, we see this code over here, but what I
want you to do is instead of this being I less than equal to N and J less than or equal to N.
Let's just pretend that it was just I less than in N.J., less than a in here is there's not a lot going
on in here besides this count plus plus.
So let's use that as our basic operation.
So go ahead and pause this video and see if you can work it out in your head or on paper what you think
the time complexity would be.
And if you believe that it is o n squared, think about why would it be n squared?
So, mind you, we're not talking about this equals sign right now.
Just pretend it's I less than an and j less than in.
OK, so if you went ahead and looked at that, you might have thought, OK, well, I'm going to first
look at this interview and see that this happens in times.
And of course, that's we're still talking about this G8 less than in and I listen in now with the equal
sign right now.
So if I go in times here and then that whole thing is happening in times here so I can go in times in
and in times in is in squared.
That would be the correct way of thinking, and that is in fact correct.
If you just have I listen in and listen in here, it would be a time complexity of o of n squared.
And if we think back to some math that some of you might have done before or not, that would result
in kind of a curved line here.
If you think back to Paulette Parabolas and such, we're just looking at these Cartesian planes here.
We're going to have a curve graph like this, and I know it's kind of a bad, poorly drawn graph, but
you can get the picture of it.
OK, so now let's look at this one.
So if we have less than or equal to N is pretty much the same thing.
But what we're doing is it's just it's just like only slightly more complicated as far as these terms
here.
But essentially we're doing the same thing.
This happens in plus one times because we're doing less than or equal to.
It's one more now.
And same with this outer loop.
So in +1 times, in +1, we get n squared plus two in plus one.
Like I was mentioning before, we're going to drop the constants, so we're going to drop this added
cost around here and we're going to drop this constant here.
Similar to when we were back here, we had this two in and we got rid of the two.
We're going to go ahead and do that for both of these, and then we have O and Squared Plus in.
But actually, like I mentioned before, we're really only interested in the largest term.
So we're even going to get rid of this in because this is bigger.
This is basically a worse if you were to just have of in and o n squared and compare them side by side.
You could draw this on your graph here.
You would notice that in squared ons, Owen is a worse time complexity than in it because it grows at
a faster rate.
So that is why we're going to drop the N because we really only care about the term that's like the
largest, the largest magnitude.
OK, so hopefully this has explained enough for you to get by with the basics of Big O.
Like I said later, we're going to go into more formal analyses of these things using summations and
recurrence formulas, a little bit of math that we might have to brush up on.
But right now, this is enough for us to get by in the first part of this series.
I definitely encourage you to go online and look up more about time complexity.
If there's any gaps that are here and I will try and provide some links that can help you do that.
All right, I'll see you in the next lecture.