Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
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 . That is, given a value x and non-negative integer n, we wish to compute the summation

displaymath57568

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

   program879
Program: Program to compute tex2html_wrap_inline57574.

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

 

 

statement time
5 2
6a 2
6b 3(n+2)
6c 4(n+1)
8 2(n+1)
9a 2(n+1)
9b tex2html_wrap_inline57588
9c tex2html_wrap_inline57590
10 tex2html_wrap_inline57590
11 4(n+1)
13 2
TOTAL tex2html_wrap_inline57598
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_inline57600 and tex2html_wrap_inline57602. Both of these are arithmetic series summations . In the next section we show that the sum of the series tex2html_wrap_inline57604 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_inline57598 cycles.


next up previous contents index

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