Big O Notation and Polynomials

Date: 04/12/2001 at 10:17:29
From: Paul Statham
Subject: Big O Notation and polynomials

I have a sample question I have been practicing. It gives the 
function:

   f(x) = (x^3 - (4x^2) + 12)/(x^2 + 2)

It then asks me to plot this on an Excel worksheet and explain the 
behaviour for increasing values of x, where 0 <= x <= 20 for intervals 
of 0.2. This part I have no problem with. It then tells me to find a 
polynomial function g(x) such that both these conditions apply.

   .f(x) is O(g(x))
   .g(x) is O(f(x))

From this I presume that f(x) is the same as it was defined before, 
and have done the following calculations to get O(g(x)).

For x > 1 we have the numerator

   x^3 - 4x^2 + 12 <= x^3 + 0 + 12x^3

For x > 2 we have the denominator

   x^2 + 2 <= x^2 + 2x^2

Hence we have

   |f(x)| <= 13x^3/3x^2
           = 13x/3

giving f(x) as O(x)

First of all, is that correct? And if it is, does it mean that 
g(x) = x ?

This bit is confusing me because if that is the case, then how can    
g(x) be O(f(x)) ?

Date: 04/12/2001 at 17:31:19
From: Doctor Rob
Subject: Re: Big O Notation and polynomials

Thanks for writing to Ask Dr. Math, Paul.

You have a minor problem in the above analysis because of the
following fact. It is false that a <= b and 0 < c <= d implies that 
a/c <= b/d.  (Try a = 9, b = 10, c = 1, d = 2.)

What is true is that a <= b and c >= d > 0 implies that a/c <= b/d.  
Thus you need to find a function that is smaller than x^2 + 2, not 
greater, and still positive.  x^2 will do, and then you get

   |f(x)| <= 13*x^3/x^2 = 13*x.

This still gives f(x) = O(x), which is correct.

To prove that x = O(f(x)), you need to find a constant C and a
bound X such that x >= X implies that x <= C*f(x).

One way I like to deal with rational functions is to divide the
polynomial of larger degree by the one of smaller degree, with
remainder, and express the function that way. In this case,

   f(x) = (x^3-4*x^2+12)/(x^2+2)
        = x - 6 + (2*x+4)/(x^2+2)

Now I want to know when the fraction is smaller than a constant. The 
constant 2 happens to be convenient, but I could use any other 
positive one I want. That happens when

   (2*x+4)/(x^2+2) < 2
   x + 2 < x^2 + 2
   0 < x^2 - x

which is true for all x > 1.  Thus for all x > 1, f(x) < x - 4 < x.  
This proves that f(x) = O(x).

On the other hand, the fraction is positive for all x > -2. That 
implies that for all x > -2, f(x) > x - 6.  Now I want x - 6 > C*x for 
some C and all x >= X.  That happens if and only if (1-C)*x > 6, that 
is, x > 6/(1-C) (for C < 1).  That means that I can choose, for 
example, C = 1/2, and X = 12, and then for x >= 12, x - 6 >= (1/2)*x, 
so for x >= 12,

   f(x) > x - 6 >= (1/2)*x
   x < 2*f(x)

This means that x = O(f(x)).

You can choose g(x) = x.

It may be worth noticing that *any* polynomial g(x) of degree 1 would 
do here. You would have to adjust the constants C and bounds X, but 
that does not affect the validity of the relation, which just needs 
them to exist, and doesn't specify their sizes.

g(x) and f(x) can have that relation if |f(x)/g(x)| is bounded above 
and below by positive constants for large x. In this case, the 
constants 1 and 1/2 will do, and when you use those constants, "large" 
means x >= 12.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/