Tip:
Highlight text to annotate it
X
Having slogged through the formal definition of big O notation, I wanna
quickly turn to a couple of examples. Now, I wanna warn you up front, these are
pretty basic examples. They're not really gonna provide us with any insight that we
don't already have. But they serve as a sanity check that the big O notation's
doing what its intended purpose is. Namely to supress constant factors and low order
terms. Obviously, this simple examples will also give us some, facility with the
definition. So the first example's going to be to prove formally the following
claim. The claim states that if T of N is some polynomial of degree K, so namely. H
A N to the K. Plus all the way up to A1N + A knot. For any introgen K, positive
introjet K and any coefficient AI's positive or negative. Then. T of N is big
O N to the K. So this claim is a mathematical statement and something we'll
be able to prove as far as you know what this claim is saying is just saying big
annotation really does suppress constant factors in inordinate forms if you have a
polynomial then all you have to worry about is what is the highest power in that
polynomial and that dominates its growth as N goes to infinity. So, recall how one
goes about showing that one function is big O of another. The whole key is to find
this pair of constants, c and n knot, where c quantifies the constant multiple
of the function you're trying to prove big O of, and n knot quantifies what you mean
by, for all sufficiently large n. Now, for this proof, to keep things, very simple to
follow, but admittedly a little mysterious, I'm just gonna pull these
constants, c and n knot, out of a hat. So, I'm not gonna tell you how I derived them,
but it'll be easy to check that they work. So let's work with the constants N not
equal to one, so it's very simple choice of N not and then C, we are gonna pick to
be sum of the absolute [inaudible] of the coefficients. So the opposite value of AK
plus the opposite value of AK minus one, and so on. Remember I didn't assume that
the polynomial, the original polynomial had non negative coefficients. So I claim
these constants work, in the sense that we'll be able to prove to that, assert,
you know establish the definition of big O notation. What does that mean? Well we
need to show for all and at least one cause remember we chose and not equal to
one, T of N is [inaudible] up here is bounded above by C times and do the K,
were C is the way we chose it here underlined in red. So lets just check why
this is true. So for every positive integer N at last one. What we've just
proved. We proved T event is upper bounded by something else. So we gonna start on
the left hand side with the T event. And now we need a sequence of upper bounds
terminating with c times into k. Our choice of c underlined in red. So T then
is given as equal to this polynomial underlined in green. So what happens when
we replace each of the coefficients with the absolute value of that coefficient?
Well, when you take the absolute value of number, either it stays the same as it was
before, or it flips from negative to positive. Now, N here we know is at least
one. So if any coefficient flips from negative to positive, then the overall
number only goes up. If we apply the absolute value each of the coefficients we
get an only bigger number. So T of N is [inaudible] above By the new polynomial
where the coefficients are the absolute values of those we had before. So why is
that a useful step? Well now what we can do is we can play the same trick but with
N so it's sort of annoying how right now we have these different powers of N it
would be much nicer if we just had a common power of N so let's just replace
all of these different N's to N to the K the biggest power that shows up anywhere.
So if you replace each of these lower powers of n with higher power of n to the
power k that number only goes up. Now that coefficient are all non negative so the
overall number only goes up. So this is bounded above by, the absolute value of A.
K. Into the K. Up to absolute value of A1N to the K, plus A, not N to the K. I'm
using here that N is at least one, so higher powers of N are only bigger. And
now you'll notice this, by our choice of C underlined in red, this is exactly equal
to C times N to the K. And that's what we have to prove. We have to prove that
[inaudible] of N is a most C times N to the K, given our choice of C for every N,
at least one. And we just proved that, so, end of proof. Now there remains the
question of how did I know what the correct, what a workable value of C and N
knot were? And if you yourself want to prove that something is big O of something
else, usually what you do is you reverse engineer constants that work. So you would
go through a proof like this with a generic value of C and N knot and then
you'd say Well if only I choose C in this way, I can push the proof through. And
that tells you what C you should use. If you look at the optional video on further
examples of asymptotic notation, you'll see some examples where we derive the
constants via this reverse engineering method. But now let's turn to a second
example, or really I should say, a non example. So what we're going to prove now
is that something is not [inaudible] of something else. So I claim that for every
K. At least one. N to the K is not to go N to the K minus one. And again, this is
something you would certainly hope would be true. If this was false, there'd be
something wrong with our definition of big O notation and so really this is just to
get further comfort with the definition, how to prove something is not big O of
something else, and to verify that indeed you don't have any collapse of distinctive
powers of ploynomials, which would be a bad thing. So how would we prove that
something is not big O of something else? The most. Frequently useful proof method
is gonna be by contradiction. So, remember, proof by contradiction, you
assume what you're trying to, establish is actually false, and, from that, you do a
sequence of logical steps, culminating in something which is just patently false,
which contradicts basic axioms of mathematics, or of arithmetic. So,
suppose, in fact, n to the k was big O of n to the k minus one, so that's assuming
the opposite of what we're trying to prove. What would that mean? Well, we just
referred to the definition of Big O notation. If in fact ended [inaudible]
hypothetically were [inaudible] Big O [inaudible] k minus one then by definition
there would be two constants. A winning strategy if you like seeing and not such
that for all sufficiently large in. We have a constant multiple C, times N to the
K minus one, upper bounding N to the K. So from this, we need to derive something
which is patently false that will complete the proof. And the way, the easiest way to
do that is to cancel N to the K minus one from both sides of this inequality. And
remember since N. Is at least one and K. Is at least one it is legitimate to cancel
this N. To the K. Minus one, from both sides. And when we do that we give the
assertion that n is at most some constant c for all n at least and not. And this now
is a patently false statement. It is not the case that all positive integers are
bounded above by a constant C. In particular, C+1, or the integer right
above that is not bigger than C. So that provides the contradiction that shows that
our original assumption that N to the K is big O of N to the minus K is false. And
that proves the claim. N to the K is not big O to the [inaudible] K minus one, for
every value of K. So different powers of polynomials do not collapse. They really
are distinct, with respect to big O notation.