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.

Â