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.