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

A Simple Example-Arithmetic Series Summation

In this section we apply Axioms gif, gif and gif to the analysis of the running time of a program to compute the following simple arithmetic series summation

displaymath58211

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

   program330
Program: Program to compute tex2html_wrap_inline58213

The executable statements in Program gif comprise lines 3-6. Table gif gives the running times of each of these statements.

 

 

statement time code
3 tex2html_wrap_inline58181 result = 0
4a tex2html_wrap_inline58181 i = 1
4b tex2html_wrap_inline58219 i <= n
4c tex2html_wrap_inline58221 ++i
5 tex2html_wrap_inline58221 result += i
6 tex2html_wrap_inline58225 return result
TOTAL tex2html_wrap_inline58227
tex2html_wrap_inline58229
Table: Computing the running time of Program gif

Note that the for statement on line 4 of Program gif has been split across three lines in Table gif. This is because we analyze the running time of each of the elements of a for statement separately. The first element, the initialization code, is executed once before the first iteration of the loop. The second element, the loop termination test, is executed before each iteration of the loop begins. Altogether, the number of times the termination test is executed is one more than the number of times the loop body is executed. Finally, the third element, the loop counter increment step, is executed once per loop iteration.

Summing the entries in Table gif we get that the running time, T(n), of Program gif is

  equation368

where tex2html_wrap_inline58233 and tex2html_wrap_inline58235.


next up previous contents index

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