Discrete Mathematics for Computer Science

Comparing Growth Rates of Functions 291

The relation 0 considers seemingly different functions as being equivalent, at least in

the sense that they determine the same set O(*). For example, there are many unexpected

functions F where O(F) = O(x). Two such functions are shown in Figure 5.4.

F

14 o

12 0 x

0 XX X

10 0 x x

(^8 0) 0x x X
(^0) X XX
4X 0 xX 0000
X XOX 0000
2 x x o o o o o o0

• I I I IG
  2 4 6 8 10 12

Figure 5.4 F, G E O(x).

5.1.3 Polynomial Functions

A polynomial such as

17n^137 + 197n4 5 - 20,143n^14 + 3

is a rule for computing a function. In a calculus class, for example, a polynomial function

is usually defined as having domain and range R. For the purposes of this chapter, a poly-

nomial is a rule for defining a partial function with domain of definition N and codomain

[0, 00).

Definition 4. A polynomial function (of n) of degree k is a function

P(n) = ak nk + ak-1 nk-1 + • • -+ a2 n2 + aI n + ao

where ak 0 0. The zero polynomial of n is the function F(n) = 0. The zero polynomial

has degree - 1. In general, a polynomial function is a polynomial function of any degree.

(You must read this definition carefully in other contexts, because some authors say the

zero polynomial has degree 0.)

According to the conventions of this section, for n E N, the polynomial function is
defined at n if the polynomial of degree k, evaluated at n, gives a non-negative value. Also,
by convention, P(n) should be defined for all but finitely many n's. For the polynomial

P(n) = aknk + ak-1 nk-1 + • • • + a2 n2 + al n + ao

(where ak 0 0) to satisfy this assumption, it is necessary that ai > 0.
The first result about polynomials shows that polynomials of different degree have
different growth rates. The essential step in this proof is true in the more general case of
the real numbers. We state the general result first.