Data Structures and Algorithms with Object-Oriented Design Patterns in C++

## Example-Geometric Series Summation Again

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 !