
Big O notation is the final tool for analyzing algorithms

that you need to know about before we can analyze Alice algorithm.

As we've just seen even talking about worstcase running time

can be a bit tricky if we're trying to be very precise.

We have to identify the worstcase input in detail, which can be counter intuitive

and then work through a lot of different cases.

And also as we noticed it's annoying to have to count every single step an algorithm makes.

So for example if you have two algorithms and one had a running time of 2n²+23 time steps

and the other one had 2n²+27 time steps, you wouldn't really care about the 23 or the 27.

You would say that essentially they have the same running time.

So we are going to introduce a huge simplification

to stating running times and that is called Big Onotation.

If you've had an algorithm course before, you should already be familiar with this

but we'll review it here just to make sure you understand.

So let's say we have two algorithms, algorithm A and algorithm B,

and algorithm A has a running time 3n²n+10 for an input of size n,

and algorithm B has a running time of 2^n50n+256.

So what I would like you think about is which of these two algorithms you would prefer

if you don't know anything about the input other than that you're going to get different sizes.

So no other structural assumptions or anything else that you know.

And I would like you to check this box if you think it's algorithm A that if you take

in general and this box if you think it's algorithm B.