[MUSIC]

So, now you have a lot of practice computing asymptotic bounds.

Which means those big O classes for various pieces of code.

And when we're thinking about a piece of code that's executed on a given input.

But what we'd like to do is step back and think about our original problem.

And our original problem was measuring the performance of an algorithm,

which was a strategy for solving a problem.

And so that means that we don't want to just focus in on a single input.

We wanna think about how the algorithm behaves for all inputs.

And so, by the end of this video, you'll be able to define what it means to talk

about the worst case, average case, and best case performance of an algorithm.

And talk about how that really talks

about the various inputs that we might have to come across.

And then we'll talk about, also, why each of these is used.

So, let's think back to this big picture we have of an algorithm as a problem

solving strategy or machine.

That takes some input and produces output, and the performance that we've been

focusing on is the time that it takes for the algorithm to do this.

To report back the answer, given the input.

So in the example that we've talked about way back when when we first started.

We were looking at the hasLetter method, which took as its input a word,

which was a string.

And a character which was the letter that we were looking for in that word.

And then it returned either true or

false based on whether the character was found inside the string.

Now, as we saw when we were counting operations, depending on the specific

word and letter combination, our algorithm behaved a little bit differently.

It took a different number of operations, in with each one of these cases.

So even if we were looking at the exact same word, so

that a fixed length word, and one character.

We weren't changing the number of characters we were looking for.

We could still have quite different behavior in terms of the number of

operations that our algorithm required before it could output the answer.

And so what we'd like to do now is capture that variability in

terms of the algorithm run time.

And talk about the different contexts we might care about.

So we might be optimistic and say, in the best possible case

how short might be my wait, how quick might my algorithm be?

So, if I give the algorithms just the most beautiful input,

whatever beautiful means, then how quick can it respond to me?

And now still this input is going to be of a fixed size n.

So, we don't expect the algorithm to be very quick,

no matter what size input we have.

So we're just thinking about, within all the inputs of size n,

what's the best possible behavior of my algorithm.

And so thinking back to the hasLetter method,

when is this algorithm the quickest?

When does it have to run very few operations?

Well, think back to what we do.

We start at the beginning and

we look for our letter in every possible position of our string.

So if we found our letter at the very beginning, if our letter was the very

first letter of this string, then we'd be able to quit while we were ahead.

We'd be able to return out of the method very quickly.

So the best case for this method, is when the word that we've input,

starts with the letter that we're looking for.

And in that case, well, this algorithm just really needs to do one check, really.

It just compares the letter that we're looking for

with a character at the first position of the string, and that takes constant time.

So in the best case, this method is a constant-time method.