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

Another Example-Horner's Rule

 

In this section we apply Axioms gif, gif, gif and gif to the analysis of the running time of a program which evaluates the value of a polynomial. I.e., given the n+1 coefficients tex2html_wrap_inline58245, and a value x, we wish to compute the following summation

displaymath58241

The usual way to evaluate such polynomials is to use Horner's rule , which is an algorithm to compute the summation without requiring the computation of arbitrary powers of x. The algorithm to compute this summation is given in Program gif. Table gif gives the running times of each of the executable statements in Program gif.

   program394
Program: Program to compute tex2html_wrap_inline58251 using Horner's rule

 

 

statement time
3 tex2html_wrap_inline58239
4a tex2html_wrap_inline58255
4b tex2html_wrap_inline58219
4c tex2html_wrap_inline58259
5 tex2html_wrap_inline58261
6 tex2html_wrap_inline58225
TOTAL tex2html_wrap_inline58265
tex2html_wrap_inline58267
Table: Computing the running time of Program gif

Summing the entries in Table gif we get that the running time, T(n), of Program gif is

  equation414

where tex2html_wrap_inline58271 and tex2html_wrap_inline58273.


next up previous contents index

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