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, these 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(n) is some polynomial of degree "k", so namely
ak n^k. Plus all the way up to a1 N + a0. For any integer "k", positive
integer "k" and any coefficients ai's positive or negative. Then: T(n) is big
O of n^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, it's just saying big O
notation really does suppress constant factors and lower order terms. 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 n0, where c quantifies the constant multiple
of the function you're trying to prove big O of, and n0 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 n0, 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 n0
equal to one, so it's very simple choice of n0 and then "c" we are gonna pick to
be sum of the absolute values of the coefficients. So the absolute value of "ak"
plus the absolute value of "a(k-1)", and so on. Remember I didn't assume that
the pol..., 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 that for all "n" at least one (cause remember we chose n0 equal to
one), T(n) (this polynomial up here) is bounded above by "c" times "n^k",
where "c" is the way we chose it here, underlined in red. So let's just check why
this is true. So, for every positive integer "n" at least one, what do we need
to prove? We need to prove T(n) is upper bounded by something else. So we're gonna start on
the left hand side with T(n). And now we need a sequence of upper bounds
terminating with "c" times "n^k" (our choice of c underlined in red). So T(n)
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, you take the absolute value of a 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. So if we apply the absolute value of each of the coefficients we
get an only bigger number. So T(n) is bounded above by the new polynomial
where the coefficients are the absolute values of those that we had before. So why was
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 by "n^k", the biggest power of "n" that shows up anywhere.
So if you replace each of these lower powers of "n" with the higher power "n^k",
that number only goes up. Now, the coefficients are all non negative so the
overall number only goes up. So this is bounded above by "the absolute value of ak" "n^k"
...up to "absolute value of a1" "n^k" ...plus "a0" "n^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^k". And that's what we have to prove. We have to prove that
T(n) is at most "c" times "n^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 "n0"
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 "n0" and then
you'd say, "Ahh, 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 big O of something else. So I claim that for every
"k" at least 1, "n^k" is not O(n^(k-1)). 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^k was big O of n^(k-1), 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 "n^k"
hypothetically were Big O of n^(k-1) then by definition
there would be two constants, a winning strategy if you like, "c" and "n0" such
that for all sufficiently large "n", we have a constant multiple "c" times "n^(k-1)"
upper bounding "n^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^(k-1)" from both sides of this inequality. And
remember since "n" is at least one and "k" is at least one, it's legitimate to cancel
this "n^(k-1)" from both sides. And when we do that we get the
assertion that "n" is at most some constant "c" for all "n" at least "n0". 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^k" is big O of "n^(k-1)" is false. And
that proves the claim. "n^k" is not big O of "n^(k-1)", for
every value of "k". So different powers of polynomials do not collapse. They really
are distinct, with respect to big O notation.