Average Running Times

In the previous section, we found the function, , which gives the running time of Program  as a function both of number of inputs, n, and of the actual input values. Suppose instead we are interested in a function which gives the running time on average for n inputs, regardless of the values of those inputs. In other words, if we run Program , a large number of times on a selection of random inputs of length n, what will the average running time be?

We can write the sum of the running times given in Table  in the following form

where is the probability that line 6 of the program is executed. The probability is given by

I.e., is the probability that the array entry, , is larger than the maximum of all the preceding array entries, .

In order to determine , we need to know (or to assume) something about the distribution of input values. For example, if we know a priori that the array passed to the function FindMaximum is ordered from smallest to largest, then we know that . Conversely, if we know that the array is ordered from largest to smallest, then we know that .

In the general case, we have no a priori knowledge of the distribution of the values in the input array. In this case, consider the iteration of the loop. In this iteration is compared with the maximum of the i values, preceding it in the array. Line 6 of Program  is only executed if is the largest of the i+1 values . All things being equal, we can say that this will happen with probability 1/(i+1). Thus

Substituting this expression for in Equation  and simplifying the result we get

where , is the harmonic number .

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