Data Structures and Algorithms with Object-Oriented Design Patterns in C++

## A Simple Example-Arithmetic Series Summation

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

The algorithm to compute this summation is given in Program .

Program: Program to compute

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

 statement time code 3 result = 0 4a i = 1 4b i <= n 4c ++i 5 result += i 6 return result TOTAL

Note that the for statement on line 4 of Program  has been split across three lines in Table . 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  we get that the running time, T(n), of Program  is

where and .