0:00

Okay, so now that we have these asymptotic notations Big O, omega and theta.

Now we can use these kind of, of notations and their definitions to put upper

bounds for example, on the running time of functions, and use these to give us a bet,

an id, to give us a good idea of how the algorithm is going to behave.

When we use an upper bound,

we are going to say that the algorithm is not going to get worse than this, or

the running time is not going to get worse than this.

When we put an upper on we put a lower bound,

we are basically saying, this is the best the algorithm can do.

And usually, the algorithms do not necessarily have even to

achieve these running times.

So if I put a lower bound of 2 to the N on an algorithm, it doesn't mean that

it's going to, it's going to, there are instances it's going to reach 2 to the n.

It might be that for

every instance of the input is going to be doing much more than 2 to the n.

But still, that makes 2 to the n,

it doesn't violate the fact that 2 to the n is a lower bound.

Now, of course, the, the, one of the issues that we have to make sure or to,

to make certain that everyone understands, is that when we put an upper bound or

lower bound, if all I'm saying is that give me a lower bound and

the running time of an algorithm, of course you know, one can say 0,

every algorithm is going to take more than 0 seconds, right?

Or more than, it's going to perform more than zero operations.

Now that is not an interesting lower bound.

Even though we're saying we want lower bounds and

upper bounds, we are often implicitly asking for the tightest possible, okay?

For the tightest running time possible.

And when we, let's now go back to the, to one of these which we are going to be

using most of the time in this course, which is the big connotation.

And just a, a, a reminder,

that we say that F of N is O of G of N,

if there exists two constants such

that F of N is smaller than C times G of N for

every n greater than n 0.

Now let's use this definition, and try to establish for

example, some some upper bound on some functions.

And I will take as an example, f of n equal

1,000 plus 17n plus 2n squared.

2:34

And I want to show, as I said before when we were talking about the growth of

functions, that we can ignore the lower terms, and

we can ignore multiplicative constant factors.

I can ignore the 2, 17 and thousand, and so on.

And just say that this is going to grow in the order of n squared.

Where does, where does that come from?

Or am I just doing some sort of tricks?

If we come actually now and understand the definition of big O, we will see that in

fact, F of N, is O of G of N, where OG of N is n squared.

How do I get that f of n is, is O of G of N in this case?

3:13

We have to go back to the definition.

The definition says that if to claim that f of n is O of g of n,

I have to find two constants, C greater than 0, n 0 greater than or equal to 0.

Such that this is going to be bounded from above by

C times n squared for every n greater than or equal to n 0.

Now, we can guess some of these numbers, but

also we can go about it a bit more systematically.

Remember that

I'm interested in finding f of n is smaller than or equal to something.

All right?

So, the way I would do it, is that f of n is 1000 plus 17n plus 2n squared.

4:20

I can say that 1,000 is smaller than or equal to 1,000 n squared.

If you take a number, and you'll now multiply it by a positive number,

of course this is smaller than or equal to this, right?

1000 is smaller than, or equal to 1000n squared, except if n equals 0.

Right?

If n equals 0, 1000 is not smaller than or equal to 1000 time n squared.

If n is 1, 1000 is smaller than or equal to 1000 n squared.

If n is 2, this is where this starts growing faster now.

1000 is much smaller than 1000 times 4, and so on.

So for this to hold, I have to start now putting conditions that n has to

be greater than or equal to 1.

Okay?

For me to make this jump that 1000 is smaller than or equal to 1000 n squared,

I have to have this assumption that n is greater than or equal to 1.

5:18

So this is smaller than this, plus 17 n,

17 n also is smaller than 17 n squared.

Okay?

Again, 17 n is smaller than 17 n squared because we have n is, n squared is,

is larger than n, and we can make this assumption, yeah, okay?

In this case, even if n is 0, 17 n is smaller than or

equal to 17 times n squared.

Okay?

So we don't have to modify this condition.

This is still going to hold.

I cannot lower it to 0 because it's going to violate this one.

Plus, 2n squared is smaller than or equal to 2n squared, okay?

Now, you might be asking now, but also 1000 is smaller than or equal to 1000n.

Or you might be asking, but 1000 is also smaller than or

equal to 1000 n the fifth, which is true for this condition.

Why did I, you choose N squared?

Again, keep in mind that I'm trying to establish that this is O of n squared.

So I would like to see N squared here, because once I see N squared here,

now this is a term that's easy for

me to manipulate, because now I can add these numbers here and

say 1,000 plus 17 plus 2 is 1,019 n squared.

Right?

So now I have this function, that is guaranteed to be smaller than or

equal to 1,019 n squared, for every n greater than or equal to 1.

6:53

Again, I can basically say that 1,000, plus 17 n plus 2n squared,

is smaller than or equal to 1,019 n squared for

every N greater than or equal to 1, okay?

Now, when I look at something like this, and look at this kind of definition,

now you can start seeing some sort of correspondence.

This, is F of N.

7:52

The last thing I need to do, is try to find C and

n 0, but they actually jump at you.

Once you look at it like this, because, if you look at this, just call this C,

call this n 0.

We have to make sure that this if I call them C and

n 0, that they satisfy the, the properties of the finishin.

The finishin says that C is greater, has to be greater than 0.

It is greater than zero.

For example, if doing this exercise I got to minus three here,

I couldn't call minus three C, because C has to be greater than 0.

8:33

I call this n 0.

N 0 has to be greater than or equal to zero.

1 is greater than or equal to 0.

So I am done.

Okay? I am done.

I have showed that I can find C,

I can find an n 0, such that this function is smaller than or

equal to C times n squared, for every n greater than or equal to n0.

The C is 1,019, then n0 equal 1.

So, this is what I meant in the beginning when I said that we

will be doing rigorous mathematical reasoning rather than proving.

I'm not saying that this is a full proof that this is a,

that this is true, but we can argue, or this is, this is not the technique for

proving formally that f of n is g of n, and it might not work for many cases.

But it's easier for me to reason about how why this is smaller than C times this,

by using this kind of technique, okay?

So here, I just showed a specific value of C, a specific value of C of, of n0,

such that I can bound f of n from above by C times n squared, for

every value of n greater than or equal to 1.

And this is how we would basically do this kind of, of of exercise.

Now, if this was omega, for example if I said,

f of n is omega of, of n squared, we can do a similar exercise.

But then, we shouldn't be focusing on showing it is smaller than or

equal to something else.

We should be focusing on greater than or equal to something else, okay?

And the last thing I want to say is that, if you want to show a function f is theta

of g of n, and you have showed that the function f f is O of g of n,

and the function f is omega of g of n, in fact, you are done.

Because it's easy to, to see that if f

is f of n, is big O of g of n,

10:44

You can conclude from these two that f

of n is theta of g of n, okay?

In fact, you can also go this way.

If you prove that f of n is theta of g of n, you have, in fact, proved that f

of n is O of g of n, and at the same time, f of n is omega of g of n.