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 .

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 .

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