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.