An example-Geometric Series Summation

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

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 .

program872
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

2 2

3 2

4 3(n+2)

5 2(n+1)

6 2(n+1)

7

8

9

10 4(n+1)

11 4(n+1)

12 2

TOTAL

Table: Computing the running time of Program .

**Table:** Computing the running time of Program .
statement	time
2	2
3	2
4	3(n+2)
5	2(n+1)
6	2(n+1)
7
8
9
10	4(n+1)
11	4(n+1)
12	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.