Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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).

I'm not sure about this proof. But even if it does work, it only holds for
natural numbers, and I'm curious about other sets, like R. 

I really need your comment about it.



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

Your response is really appreciated.



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;
try something similar before asking your next question), I'll offer a
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!

If you have any questions about this or need more help, please write back
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/