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

displaymath57445

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

   program357
Program: Program to compute tex2html_wrap_inline57447.

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

 

 

statement time code
5 tex2html_wrap_inline57415 result = 0
6a tex2html_wrap_inline57415 i = 1
6b tex2html_wrap_inline57453 i <= n
6c tex2html_wrap_inline57455 ++i
7 tex2html_wrap_inline57455 result += i
8 tex2html_wrap_inline57459 return result
TOTAL tex2html_wrap_inline57461
tex2html_wrap_inline57463
Table: Computing the running time of Program gif.

Note that the for statement on line 6 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

  equation396

where tex2html_wrap_inline57467 and tex2html_wrap_inline57469.


next up previous contents index

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