Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
In this example we revisit the problem of computing a
geometric series summation .
We have already seen an algorithm to compute this summation
in Section 
(Program ).
This algorithm was shown to take 
cycles.
The problem of computing the geometric series summation
is identical to that of computing the value of a polynomial
in which all of the coefficients are one.
This suggests that we could make use of
Horner's rule
as discussed in Section .
An algorithm to compute a geometric series summation
using Horner's rule is given in Program .
Program: Program to compute 
using Horner's rule
The executable statements in Program
comprise lines 3-6.
Table gives the running times,
as given by the simplified model,
for each of these statements.
| statement | time |
| 3 | 2 |
| 4a | 2 |
| 4b | 3(n+2) |
| 4c | 4(n+1) |
| 5 | 6(n+1) |
| 6 | 2 |
| TOTAL | 13n+22 |
In Programs and
we have seen two different algorithms to compute the same
geometric series summation.
We determined the running time of the former to be
cycles
and of the latter to be 13n+22 cycles.
In particular, note that for all non-negative values of n,
.
Hence, according to our simplified model of the computer,
Program , which uses Horner's rule,
always runs faster than Program !
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.