Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

About Polynomials Again

 

In this section we reexamine the asymptotic behavior of polynomials in n. In Section gif we showed that tex2html_wrap_inline58743. That is, f(n) grows asymptotically no more quickly than tex2html_wrap_inline59251. This time we are interested in the asymptotic lower bound rather than the asymptotic upper bound. We will see that as n gets large, the term involving tex2html_wrap_inline59251 also dominates the lower bound in the sense that f(n) grows asymptotically as quickly as tex2html_wrap_inline59251. That is, that tex2html_wrap_inline59261.

Theorem  Consider a polynomial  in n of the form

eqnarray1573

where tex2html_wrap_inline58741. Then tex2html_wrap_inline59261.

extbfProof We begin by taking the term tex2html_wrap_inline59269 out of the summation:

eqnarray1827

Since, n is a non-negative integer and tex2html_wrap_inline58741, the term tex2html_wrap_inline59269 is positive. For each of the remaining terms in the summation, tex2html_wrap_inline59277. Hence

eqnarray1833

Note that for integers tex2html_wrap_inline58757, tex2html_wrap_inline59281 for tex2html_wrap_inline59283. Thus

eqnarray1847

Consider the term in parentheses on the right. What we need to do is to find a positive constant c and an integer tex2html_wrap_inline58265 so that for all integers tex2html_wrap_inline58299 this term is greater than or equal to c:

displaymath59243

We choose the value tex2html_wrap_inline58265 for which the term is greater than zero:

eqnarray1864

The value tex2html_wrap_inline59295 will suffice! Thus

  eqnarray1878

From Equation gif we see that we have found the constants tex2html_wrap_inline58265 and c, such that for all tex2html_wrap_inline58299, tex2html_wrap_inline59303. Thus, tex2html_wrap_inline59261.

This property of the asymptotic behavior of polynomials is used extensively. In fact, whenever we have a function, which is a polynomial in n, tex2html_wrap_inline58775 we will immediately ``drop'' the less significant terms (i.e., terms involving powers of n which are less than m), as well as the leading coefficient, tex2html_wrap_inline58781, to write tex2html_wrap_inline59261.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.