0:00

This video is for those of you who want some additional practice with asymptotic

notation. And we're gonna go through three additional optional examples. Let's start

with the first one. So the point of this first example is to show how to formally

prove that one function is big O of another. So the function that I want to

work with is two raised to the N plus ten, okay, so it's the two to the N function

that you're all familiar with, we're going to shift it by ten and the claim is that

this function is big O of two to the N, so without the ten. So how would one prove

such a claim? Well lets go back to the definition of what it means for one

function to be big O over another, what we have to prove is we need to show that

there exists two constants, so that for all sufficiently large N meaning N bigger

than N-nought, our left hand side, so the function should be N plus ten is bounded

above by a constant multiple C times the function on right hand side to the N.

Right so for all sufficiently large N the function is bounded above by a constant

multiple of two to the N. So unlike the first basic example where I just pulled the

two constants out of a hat let's actually start the proof and see how you'd reverse

engineer the suitable choice of these two constants. So, what a proof would

look like, it would start with two to the N plus ten, on the left-hand side, and

then there'd be a chain of inequalities, terminating in this, C times two to the N.

So, let's just go ahead and start such a proof, and see what we might do. So, if we

start with two to the N plus ten on the left-hand side, what would our first step

look like? Well, this 10's really annoying, so it makes sense to separate it

out. So you could write two to the N plus ten as the product of two terms. Two to

the ten, and then the two to the N. Also known as just 1024 times two to the N. And

now we're in, looking in really good shape. So if you look at where we are so

far, and where we want to get to, it seems like we should be choosing our constant C

to be 1024. So if we choose C to be 1024 and we don't have to be clever with N-nought

we can just set that equal to one, then indeed star holds to the desired inequality and

remember to prove that one function is big O of another all you gotta do is come up

with one pair of constants that works and we've just reverse engineered it just

choosing the constant C to be 1024 and N-nought to be one works so this proves that

two to the N plus ten is big O over two to the N. Next let's turn to another non

example how, of a function which is not big O over another. And so this will look

superficially similar to the previous one. Instead of taking, adding ten in the

exponent of the function two to the N, I'm gonna multiply by ten in the exponent. And

the claim is if you multiply by ten in the exponent then this is not the same

asymptotically as two to the N. So once again, usually the way you prove one thing

is not big O of another is by contridiction. So we're going to assume

the contrary, that two to the ten N is in fact big O of two to the N. What would it

mean if that were true? Well, by the definition of big O notation, that would

mean there are constant C and N-nought. So that for all large N, two to the ten

N is bounded above by C times 2 to the N. So to complete the proof what we have

to do is go from this assumption and derive something which is obviously false

but that's easy to do just by cancelling this 2 of the N terms from both sides.

So if we divide both sides by 2 to the N, which is a positive number since N is

positive, what we find would be a logical consequence of our assumption would be

that two raised to the nine N is bounded above by some fixed constant C for all N

at least N-nought. But this inequality of course is certainly false. The right hand

side is some fixed constant independent of N. The left hand side is going to infinity

as N grows large. So there's no way this inequality holds for arbitrarily large N.

So that concludes the proof by contradiction. This means our assumption

was not the case, and indeed it is not the case that two to the ten N is big O of two to

the N. So our third and final example is a little bit more complicated than the first

two. It'll give us some practice using theta notation. Recall that while big O is

analogous to saying one function is less than or equal to another, theta notation

is in the spirit of saying one function is equal asymptotically to another. So here's

gonna be the formal claim we're gonna prove, for every pair of functions F and

G, both of these functions are defined on the positive integers, the claim is that

it doesn't matter, up to a constant factors, whether we take point wise

maximum of the two functions or whether we take the point wise sum of the two

functions. So let me make sure it's clear that you know I mean by the point wise

maximum by max F and G. So, if you look at the two functions, both functions of N,

maybe we have F being this green function here and we have g hooked to this red

function. Then by the point wise maximum max(F,G) just means the upper

envelope of these two functions. So that's gonna be this blue function. So lets now

turn to the proof of this claim that the point wise function of these two function

is theta of the sum of two functions. So let's recall what theta means formally.

What it means is that the function on the left can be sandwiched between the

constant multiples of the function on the right. So we need to exhibit both the

usual N-nought but also two constants, the small one, C1, and the big one, C2, so

that the point wise maximum(F,G), whatever that may be, is wedged in between

C1 and C2 times F(N) plus G(N), respectively. So to see where these

constants C1 and C2 are going to come from, let's observe the following

inequalities. So no matter what N is, any positive integer N, we have the following.

Suppose we take the larger of F of N and G of N. And remember now, we've fixed the

value of N, and it's just some integer, you know, like 23. And now F of N and G of

N are theirselves, just numbers. You know, maybe they're 57 and 74, or whatever. And

if you take the larger of F of N and G of N, that's certainly no more than the sum

of F of N plus G of N. Now, I'm using, in this inequality, that F and G are

positive. And that's something I've been assuming throughout the course so far.

Here, I wanna be explicit about it, we're assuming that F and G cannot output

negative numbers. Whatever integer you feed in, you get out something positive.

Now, the functions we care about are things like the running time of

algorithms, so there's really no reason for us to pollute our thinking with

negative numbers. So, we're just gonna always be assuming in this class, positive

numbers. And I'm actually using it here, the right hand side is the sum of two

things, is bigger than just either one of the constituent summants. Secondly. If we

double the larger of F of N and G of N well that's going to exceed the sum of F of N

plus G of N, right? Because on the right hand side we have a big number plus a

small number and then on the left hand side we have two copies of the big number

so that is going to be something larger, now it's gonna be convenient it's gonna be

more obvious what's going on if I divide both of these sides by two so that the

maximum of F of N and G of N is at least half of F of N plus G of N that is at least half

of the average and now we're pretty much home free right so what does this say.

This says that for every possible N, the maximums wedged between suitable multiples

of the sum. So one-half of F of N plus G of N. There's a lower bound on the

maximum. This is just the second inequality that we derived. And by the

first inequality that's bounded above by once times the sum. And this holds no

matter what N is, [inaudible] at least one. And this is exactly what it means to

prove that one function is theta of another. We've shown that for all N, not

just for insuffiently large, but in fact for all N. The pointwise maximum of F and

G is wedged between suitable constant multiples of their sum. And again, just to

be explicit, the certifying choices of constants are N-nought equals one. The

smaller constant is one half. And the bigger constant equals one. And that

completes the proof.