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.