|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
In this section we apply Axioms 
, , and
to the analysis of the running time of a program
which evaluates the value of a polynomial.
That is, given the n+1 coefficients 
,
and a value x, we wish to compute the following summation
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 .
Table gives the running times of each of the
executable statements in Program .
Program: Program to compute 
using Horner's rule.
| statement | time |
| 5 |  |
| 6a |  |
| 6b |  |
| 6c |  |
| 7 |  |
| 8 |  |
| TOTAL |  |
 |
Summing the entries in Table
we get that the running time, T(n),
of Program is
where 
and 
.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.
