Associated Topics || Dr. Math Home || Search Dr. Math

Proving that f = O(g) Whenever deg(f) <= deg(g)

```Date: 04/20/2010 at 15:40:15
From: Akram
Subject: f=O(g) whenever deg(f)<=deg(g) , can we formally prove it ?

It's common knowledge that f(n) = O(g(n)) whenever f(n) and g(n) are
polynomials with deg(f) <= deg(g).

Roughly speaking, I understand big O notation as saying that g(n) can
eventully beat f(n) in terms of growth even with the help of a positive
constant. By "eventually," I mean when n gets large enough, or when
n >= n_0. (Sorry for the vulgar explanation, which needs to become
more formal.)

For example: if f(n)= 100n and g(n) = n^2, then f(n) = O(g(n)).

This makes sense to me, and I can prove it algebraically by finding the
two positive integers, C = 1 and n_0 = 100, such that

0 <= f(n) <= Cg(n)

for all n >= n_0

And I can observe this relationship in the growth of the functions when I
plot them together in any graphing software.

But how can we generalize that f = O(g) whenever deg(f) <= deg(g)? and how
can we formally prove this generalization?

I tried mathematical induction to at least prove it for the natural number
set, as follows:

When n = 1, both f(n) and g(n) are constant functions, so f(n) = O(n)

When f(n) = O(g(n)),

deg(f(n + 1)) = deg(f(n))

AND

deg(g(n + 1)) = deg(g(n)),

So f(n) = O(n).

natural numbers, and I'm curious about other sets, like R.

```

```
Date: 04/28/2010 at 18:58:38
From: Akram
Subject: f=O(g) whenever deg(f)<=deg(g) , can we formally prove it ?

```

```
Date: 05/02/2010 at 20:03:27
From: Doctor Vogler
Subject: Re: f=O(g) whenever deg(f)<=deg(g) , can we formally prove it ?

Hi Akram,

Thanks for writing to Dr. Math -- and for letting us know you're still
interested in an answer. Sorry for the delay.

Of course, we can prove this formally. It just takes a little careful
analysis to figure out what the constants have to be. It might help to try
this for a few specific examples first, like

n^2 + 1 = O(n^2)

or

n^3 + n + 1 = O(n^3 - 1).

If you can formally prove it for a particular pair of functions, then try
a harder pair (or, in any case, another pair) until you figure out a
strategy that will work for all pairs of polynomials.

Rather than leave you only with that advice (which is still good advice;
general strategy.

Let d = deg(g), so that deg(f) <= d. Also let M be the sum of the absolute
values of all of the coefficients of f(n).

It follows that

|f(n)| <= M*n^d

whenever n >= 1. Can you explain why? (Hint: start with the triangle
inequality.)

Next, let A be the leading coefficient of g(n) and let B be the sum of the
absolute values of all of the *other* coefficients of g(n). Now explain
why A is nonzero and

|g(n) - A*n^d| <= B*n^(d - 1)

whenever n >= 1. It follows that, in particular,

-(g(n) - A*n^d) <= B*n^(d - 1).

The above is true in either case; but in the following, I will assume that
A > 0. (If A < 0, then you could just use the argument with g(n) replacing
-g(n), and then take the final C and negate it. But it would be a
little funny to use a negative function in a big-O.) And of course, B >= 0
by definition.

Next, use the previous inequality to prove that, when n >= 1,

A*n^d - B*n^(d - 1) <= g(n).

Now all we need to do is get

M*n^d <= C*(A*n^d - B*n^(d - 1)),

and then we'll be done! If it weren't for that pesky B, then we could just
take C = M/A. But B might actually be larger than A, so we can't simply
subtract B from A. Fortunately for us, B is the coefficient of a
lower-degree term, and we can use that to our advantage.

Let's require n be large enough that the B term doesn't reduce the A term
by more than 1/2. That results in the following argument:

Let n_0 = max(1, 2B/A). If n >= n_0, then we have

n >= 2B/A
(A*n)/2 >= B
(A*n^d)/2 >= B*n^(d - 1)
A*n^d - (A*n^d)/2 >= B*n^(d - 1)
A*n^d - B*n^(d - 1) >= (A*n^d)/2

Now we take C = 2M/A. Since n >= n_0 >= 1, we have

|f(n)| <= M*n^d = (A*C/2)*n^d = C*(A*n^d)/2
<= C*(A*n^d - B*n^(d - 1))
<= C*g(n).

And there we have it!

and show me what you have been able to do, and I will try to offer further
suggestions.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Polynomials

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search