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

### 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/
```
Associated Topics:
High School Equations, Graphs, Translations
High School Functions
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