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

Example-Prefix Sums

In this section, we will determine a tight big-oh bound on the running time of a program to compute the series of sums , , ..., , where

An algorithm to compute this series of summations is given in Program . Table  summarizes the running time calculation.

Program: Program to compute for

 statement time 3a O(1) 3b 3c 5 6a 6b 6c 7 8 TOTAL

Usually the easiest way to analyze program which contains nested loops is to start with the body of the inner-most loop. In Program , the inner-most loop comprises lines 6 and 7. In all, a constant amount of work is done--this includes the loop body (line 7), the conditional test (line 6b) and the incrementing of the loop index (line 6c).

For a given value of j, the inner-most loop is done a total j+1 times. And since the outer loop is done for , in the worst case, the inner-most loop is done n times. Therefore, the contribution of the inner loop to the running time of one iteration of the outer loop is O(n).

The rest of the outer loop (lines 3, 5 and 8) does a constant amount of work in each iteration. This constant work is dominated by the O(n) of the inner loop. The outer loop is does exactly n iterations. Therefore, the total running time of the program is .

But is this a tight big oh bound? We might suspect that it is not, because of the worst-case assumption we made in the analysis concerning the number of times the inner loop is executed. The inner-most loop is done exactly j+1 times for . However, we did the calculation assuming the inner loop is done O(n) times, in each iteration of the outer loop. Unfortunately, in order to determine whether our answer is a tight bound, we must determine more precisely the actual running time of the program.

However, there is one approximate calculation that we can easily make. If we observe that the running time will be dominated by the work done in the inner-most loop, and that the work done in one iteration of the inner-most loop is constant, then all we need to do is to determine exactly the number of times the inner loop is actually executed. This is given by:

Therefore, the result is a tight, big-oh bound on the running time of Program .