An Example-Geometric Series Summation

Data Structures and Algorithms with Object-Oriented Design Patterns in Java

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

An algorithm to compute this summation is given in Program .

program879
Program: Program to compute .

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

statement time

5 2

6a 2

6b 3(n+2)

6c 4(n+1)

8 2(n+1)

9a 2(n+1)

9b

9c

10

11 4(n+1)

13 2

TOTAL

Table: Computing the running time of Program .

**Table:** Computing the running time of Program .
statement	time
5	2
6a	2
6b	3(n+2)
6c	4(n+1)
8	2(n+1)
9a	2(n+1)
9b
9c
10
11	4(n+1)
13	2
TOTAL

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