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

About Polynomials

 

In this section we examine the asymptotic behavior of polynomials in n. In particular, we will see that as n gets large, the term involving the highest power of n will dominate all the others. Therefore, the asymptotic behavior is determined by that term.

Theorem  Consider a polynomial  in n of the form

eqnarray1490

where tex2html_wrap_inline59517. Then tex2html_wrap_inline59519.

extbfProof Each of the terms in the summation is of the form tex2html_wrap_inline59521. Since n is non-negative, a particular term will be negative only if tex2html_wrap_inline59525. Hence, for each term in the summation, tex2html_wrap_inline59527. Recall too that we have stipulated that the coefficient of the largest power of n is positive, i.e., tex2html_wrap_inline59517.

eqnarray1498

Note that for integers tex2html_wrap_inline59533, tex2html_wrap_inline59535 for tex2html_wrap_inline59537. Thus

  equation1510

From Equation gif we see that we have found the constants tex2html_wrap_inline59539 and tex2html_wrap_inline59541, such that for all tex2html_wrap_inline59075, tex2html_wrap_inline59545. Thus, tex2html_wrap_inline59519.

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_inline59551 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_inline59557, to write tex2html_wrap_inline59519.


next up previous contents index

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