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.