So now we're going to talk about theoretical evaluation.
So remember, big O, there's two things that we need to keep in mind.
The first being we do not care about coefficients
and we will abbreviate that as co f.
And the second thing is we only care about the highest power.
Right.
So now let's let's look at some examples of this and how we might be able to evaluate this.
So let's say we have a vector.
And let's put some values in here.
We'll go five, three, six, one and eight.
And for our first algorithm, we want to find the largest number.
The largest number.
Right.
So you look at this and you say, okay, well, that's that's pretty easy to do.
All we need is a simple for loop, you know, for X in the vector.
Find the highest and that we can do that using a simple if statement.
Right.
So for this iteration right here, this is going to be an iteration.
We know that X is going to be the value in here.
Right.
So that's how many times we're going to go through and for X in vector.
Well, this is going to be the length of our vector.
So this correlates to in.
For how many items we have.
Right.
And so by doing this, find the highest logic down here.
Inside of this iteration, we can logically conclude since we're only having to iterate through the
vector one time that our big o notation is going to be o of n.
And why is it o of n?
Because we're only going through the vector one time, right?
So now let's look at a slightly different example.
Let's say we want to sort.
The vector, Right?
So for this, we'll do another four loop and we'll say four I equals zero is less than or equal to n
plus one I plus plus.
Right.
So that right here alone again is the same as above.
And that is o of n For us to sort it, we need to be able to compare and swap values in here.
So we need to have our index here for I and then we're also going to need another for loop and we'll
say it is J and we'll start J at one, right, because we want to be able to compare I and J.
So then we'll say J is less than or equal to n j plus plus, and we'll say our big notation here, let
me clean that up is o of an as well.
And these are nested right because we have o of in here and then we have another for loop below it,
which is also being executed every time that this for loop gets ran right here.
So we have our nested for loops.
We do our compare and swaps.
Sort the vector out.
And with this being a four loop, and then we have our open bracket, and then we have our other four
loop right here.
And let's label these bracket A bracket B Well, we close bracket B here and then we close bracket A
there.
And what happens with this is that for every iteration in in this A for loop, we're going to iterate
through this loop as well, right?
So I just want to make that really clear.
And with that, we're, we're going to iterate in twice, right?
And with that means that we're going to have an exponent of two.
Our highest power.
Yes, is two.
So our big notation for this would be quadratic, as we showed in the experimental.
And then our one up here.
This is linear, so obviously O of n is more performant than o of n squared.
And then if for some reason we had another for loop, so if we added another.
Nested loop.
For loop.
Now, our big rotation would be.
Oh.
Then cubed.
Right.
So hopefully that makes sense because theoretical is a lot more.
Time consider it when you're trying to evaluate your algorithm.
And I wanted to talk about big notation early on in this course is the first thing, because as we go
through and look at all these different algorithms and data structures, I want you to be familiar with
what the big notation of that algorithm or data structure could be.
And I want you to try and compute the big notations for some of these algorithms and data structures
as we go through this course so that you're able to evaluate their performance and maybe you can even
enhance them to improve their space and time complexity.
So it's really important that we really understand what bingo notation is.
So if you have any questions about it, please ask them and the Q&A section before continuing on in
this course, because I really want it to be clear as to.
How you can compute the big O notation of an algorithm.