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

An Example-Geometric Series Summation

 

In this section we consider the running time of a program to compute the following geometric series summation . I.e., given a value x and non-negative integer n, we wish to compute the summation

displaymath58625

An algorithm to compute this summation is given in Program gif.

   program814
Program: Program to compute tex2html_wrap_inline58631

Table gif gives the running time, as predicted by the simplified model, for each of the executable statements in Program gif.

 

 

statement time
3 2
4a 2
4b 3(n+2)
4c 4(n+1)
6 2(n+1)
7a 2(n+1)
7b tex2html_wrap_inline58645
7c tex2html_wrap_inline58647
8 tex2html_wrap_inline58647
9 4(n+1)
10 2
TOTAL tex2html_wrap_inline58655
Table: Computing the running time of Program gif

In order to calculate the total cycle counts, we need to evaluate the two series summations tex2html_wrap_inline58657 and tex2html_wrap_inline58659. Both of these are arithmetic series summations . In the next section we show that the sum of the series tex2html_wrap_inline58661 is n(n+1)/2. Using this result we can sum the cycle counts given in Table gif to arrive at the total running time of tex2html_wrap_inline58655 cycles.


next up previous contents index

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