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

a<u>k n^k. Plus all the way up to a<u>1 N + a<u>0. For any integer "k", positive</u></u></u>

integer "k" and any coefficients a<u>i's positive or negative. Then: T(n) is big</u>

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 n<u>0, where c quantifies the constant multiple</u>

of the function you're trying to prove big O of, and n<u>0 quantifies what you mean</u>

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<u>0, out of a hat. So, I'm not gonna tell you how I derived them,</u>

but it'll be easy to check that they work. So let's work with the constants n<u>0</u>

equal to one, so it's very simple choice of n<u>0 and then "c" we are gonna pick to</u>

be sum of the absolute values of the coefficients. So the absolute value of "a<u>k"</u>

plus the absolute value of "a<u>(k-1)", and so on. Remember I didn't assume that</u>

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 n<u>0 equal to</u>

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 a<u>k" "n^k"</u>

...up to "absolute value of a<u>1" "n^k" ...plus "a<u>0" "n^k".</u></u>

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 "n<u>0"</u>

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<u>0" and then</u>

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 "n<u>0" such</u>

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 "n<u>0". And this now</u>

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.