When we look at an algorithm, we want to try to optimize our time and space complexity.
Time is how long it takes the algorithm to run, and space refers to how much memory it takes to run.
Bingo notation is a standard mathematical notation that shows how efficient an algorithm is in the worst
case scenario relative to its input size.
And there are two ways that we can evaluate the big o of an algorithm.
The first one, which is what we're going to talk about in this lecture, is experimental.
The second one that we can talk about is going to be theoretical.
So experimental is honestly kind of what it sounds like, right?
So as we add more elements, you can envision a graph and we'll say this is zero and we'll say 110,
100, 1000, and then so on and so forth.
And as and this would be in for our input size.
And then on this axis, we would have time.
And you can imagine as the input size goes up, we see that we have a linear line.
So with it being linear, we can represent this as DT of the input size is equal to A, N plus B, So
as our input size goes up, the time is linear according to the input size.
So now when we evaluate this, right, so when we're evaluating our algorithm, there's two things that
we want.
We want less time.
And less.
Memory.
These are ideal for an algorithm.
And more time and more memory.
Are not ideal.
So again, we can look at another graph here where we have our time and our input size, and we can
also have a graph that looks something like this.
And this would be quadratic.
And so we can say for this to represent it, t of n is equal to A in squared plus B and plus C.
So we see we have two here.
But then up here this is one.
So our big notation for this would be O of n and then our big notation for this would be o of n squared.
So we don't care about coefficients.
So technically we can get rid of these because as I said, we don't care about them.
We care about the highest power, which in this case is two.
And then in this case it's one.
And that is how we're able to represent our big O notation.
And so if you wanted to do experimental
evaluation, then you would create a benchmark for your program and you would run it and you would have
input sizes of one 10,000, 1000, 10,000, and maybe even 100,000.
But in reality, sometimes, like if you if you ran 100,000 as your input size, depending on what your
algorithm is doing, that could take a substantial amount of time and you might not have that time to
to waste.
And that is where theoretical evaluation comes in.
And we will talk about theoretical big notation in the next lecture.