OK, so now we are going to get back into the asymptotic analysis of algorithms, so we talked a little
bit about this earlier on in this section of the course where we were looking at big oh and talking
about basic operations and how to figure out the time complexity of an algorithm, the runtime complexity.
And I did kind of foreshadow that we would be looking deeper into this matter and now that time has
come.
So what we're going to start out with is kind of a recap and looking at what it really means to have
bounds and what our case is like.
Best case, average case, worst case.
So let's go ahead and get started.
So a quick reminder for taking a step back.
Let's remember what we talk about when we're talking about doing asymptotic analysis on algorithms.
So the real question that we ask is what is happening to our number of operations and our function as
the input to our function gets larger and larger?
So what is the output of the function to be, how many basic operations are happening based on the input
that we have?
So here you just see a graph over on the right.
Going to use that in the next few slides as well.
So to the right, we have these two functions here.
And of course, remember that are in this the size of our input.
That's the x axis y axis is the output.
So the number of operations based on that in Big O is representative of what we call an upper bound
for the function that is the red line in the picture.
So we could say that big of an squared is a bounding function of f of T in here.
An upper bound.
So what is the upper bound really mean and why we've been using Bigo?
So the industry uses Bigo a lot.
They kind of just default to that notation rather than looking into exact balance really that often.
That's something we will look at later in the slideshow.
But there's a difference between talking about an upper bound in an exact bound.
So what's really meant by Bigo is that you were able to say bego of something if that something which
is a function in there.
So you can see if that function can be multiplied by some constants.
So like just a number, you know, an integer like two or twenty, or it doesn't have to be an issue,
but like a whole number or something, but just some constant if it can be multiplied by some constant
and it's always a greater than or equal to.
The function in question, which is the red line, then we can say that that is accurate as accurate
statement, we can say big of something.
If that is the case, we can multiply it by some constant and it will always be greater than or equal
to the red line.
For and that is for any value of and so anywhere along the x axis there.
So let's take a closer look at that.
Here we've zoomed in a little bit.
So same graph, but I'm zoomed in on the beginning.
You can see that the red line function is actually greater than what we are claiming to have be an upper
bound.
So the blue line is not later than it.
The Red Line is greater than up until about an equals 20 there.
So if we go ahead and do what we said in the previous slide and we pick some kind of constant and multiply
it, let's see what happens.
So we multiply it by some constant.
I chose 20 in this picture and you can see that when we zoom in extra close, the blue line bounding
function is always greater than or equal to the line, the red line there for any given value of in.
So the Red Line is never going to cross above the blue line.
And because that is the case that we were able to achieve this by multiplying by some constant.
We can say that the blue line is bounding our function and our function is bounded by Bigo of N squared.
So that line is then squared.
And we can say, since it's an upper bound, we are calling it o of in squared because we use the term
big o for the upper bound.
So that is what Big O means.
So let's just see if we can try something else.
Maybe we want to say, Hey, this blue line over here, I want to multiply it by some constant and bound
the red line, you know, have it be an upper bound?
Of the red line.
So right now, it's not working, let's just multiply it by a number, maybe like a hundred and maybe
OK, now maybe is not enough.
We see it still crosses under the red line somewhere.
So let's do it by like 100 billion, something that for sure would never.
You know, go below the red line, but the thing is, is that it will go below the red line.
It's some value of in.
This log in graph will actually go under the red line, no matter what constant we multiply it by.
So we will always be able to find some value in in which the red line will cross above the blue line.
And so we are unable to say that that the blue line, which is the log in, is able to be an upper bound.
So we cannot say Bigo of log in for our function.
We cannot say it's bounded by log in.
The Red Line cannot be up or bounded by it.
It can be bounded, but it cannot be up or bounded by this graph here at the log in.
So since we can't do that, let's look into lower bounds.
So the same way we did upper bounds, we can also find lower bound.
And that is denoted with Big Omega rather than big.
So here I've kind of switched the gas up and you can see that there is big omega of in on this line
there.
So we have a graph in and then we and that's in blue and then we have a graph which is n squared and
that is in red.
So we are able to call in a lower bound of the function in squared because it'll always have a slower
or equal growth rate than the Red Line.
So that's just like the upper bound we can find if we're able to find some kind of constant to multiply
the blue line function by to ensure that it's always less than an equal to, we are able to accept it
as being called a lower bound in which we would use that symbol.
Big Omega So we'd say it is lower bounded by Big Omega of in there.
So that is what a lower bound is, same thing, just kind of flipped.
So.
Yeah, if you're comparing it to the upper bound there, so you might think that, yeah, this doesn't
seem like a great definition, how would we really define the runtime complexity of the read function
in question?
You know, how do we how do we really define it by bounding it like this?
So they're a little bit loose?
If we want something more tighter and more accurate, we can use something called theta, which is upper
and lower bounds kind of squeezing our line there.
So here we have both upper and lower bounds for the red line, and they are much tighter bounds.
And both the upper and lower bounding functions, we can say that we have a theta and exact bound because
they are the same magnitude as the Red Line function.
So you notice that our red line function is in our blue, our upper blue line is two in and our lower
blue line is zero point five in.
They should remember back to when we first did Bigo and talked about basic operations and time complexity.
We can throw away these constants when we have our final answer for these bounds.
And so when you get rid of the contents, the constants you notice that they all have the same magnitude,
they are all really in.
So because of that, we can say that theta in is an exact abound on our function.
And so that's like an upper and lower sandwich unit, and we are able to use Theta because it has the
same magnitude.
It's a more exact bound.
We are able to say theta of and is a tight bound on this function.
So tip balance are sometimes pretty difficult to compute.
So that's part of why the industry often uses upper bounds because it's a little easier to compute.
Sometimes side balance are almost impossible to compute for certain situations.
So big, oh yeah, it's used a lot in industry, but it's nice to have an exact bound sometimes.
So something that I want to point out is that best case, worst case, average case, all these cases,
they are not the same thing as balance.
So Big O is not worst case.
Don't associate that with meaning.
Worst case, that is not what it means.
We talked about it in an upper bound.
Of course, these things are used together quite often.
But they don't literally mean big oh, doesn't literally mean best case.
And that kids can that kind of gets mixed up a lot in a lot of academic setting and the industry setting
as well.
Just a lot of people think that it's that it's the same thing, but it's not.
So just wanted to point that out.
It is possible to consider an upper bound for best case analysis.
So, you know, even though that doesn't necessarily make as much sense as looking in at an upper bound
for worst case analysis, it is possible.
And so I wanted to show that separation there, that they are not the exact same thing.
We're talking about two different things that you kind of use both of them to solve for time complexity
of an algorithm.
But those symbols omega and theta and big O, they are not the state of definitions of cases.
So.
I want to point that out.
So with that said, cases are something you consider before finding the balance, so you first need
to decide what you're actually looking at.
Am I looking at the worst case performance of this algorithm or the best case performance you choose
what bounding type you think is appropriate to get the best possible analysis of the algorithm?
And that's really what you're trying to do after you decide on the case.
So let's look at some examples.
Let's say we're going to do a really simple example here, but if we're doing a linear sequential search
through an array looking for a specific element.
So the best case, of course, would be if the element was the very first thing in the list.
So right when we start out, we index the first thing.
So array of zero first position.
That's the best case.
And that would just be Constantine, right?
Because we're just performing a single index on the array and we found it and we're done.
So it would be something or it could say like, you know, bingo of one.
If we wanted to put an upper bound on that, the worst case, so that's either whether we look all the
way to the very last element in the array.
So let's say the very last element is the thing we're looking for or it's not in there at all.
So either way, we had to look through the entire array of size and input in to either find it or not
find it.
We had to look through the whole array.
So that would be the worst case.
In an average case, we're just really looking at the average number of steps taken to find that element
in the array when it really could be anywhere, it could be the fourth element, it could be the hundred
thousandth element or something like that.
So it's looking at that being averaged out.
So one more thing.
There is also a little low and little omega.
So when we talked about big, oh, we were talking about it needing to be greater than or equal to the
red line when we multiply it by some constant.
And for Big Omega, it needed to be less than or equal to the Red Line when we were multiplying it by
some constant.
So little, Irwin, little Omega are just kind of looser descriptions, looser bounds on honor function,
and those are not they they don't have the or equal.
It's just littlo is just greater than and a little omega is just less than.
So that's the only difference.
You probably won't use this as much when you're doing analysis of algorithms, but I wanted to put it
out there because it is kind of part of this subject, and I believe it needed to be mentioned.
So that is all I have for the introduction to this new section in the next lectures, we will be looking
at doing these more formal analyses on the algorithms.
And so with that, I will see you in the next election, you.