Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

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 gif (Program gif). This algorithm was shown to take tex2html_wrap_inline57598 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 gif. An algorithm to compute a geometric series summation using Horner's rule is given in Program gif.

   program976
Program: Program to compute tex2html_wrap_inline57574 using Horner's rule.

The executable statements in Program gif comprise lines 5-8. Table gif gives the running times, as given by the simplified model, for each of these statements.

 

 

statement time
5 2
6a 2
6b 3(n+2)
6c 4(n+1)
7 6(n+1)
8 2
TOTAL 13n+22
Table: Computing the running time of Program gif.

In Programs gif and gif we have seen two different algorithms to compute the same geometric series summation. We determined the running time of the former to be tex2html_wrap_inline57598 cycles and of the latter to be 13n+22 cycles. In particular, note that for all non-negative values of n, tex2html_wrap_inline57662. Hence, according to our simplified model of the computer, Program gif, which uses Horner's rule, always runs faster than Program gif!


next up previous contents index

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