Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Yet Another Example-Finding the Largest Element of an Array

In this section we consider the problem of finding the largest element of an array. I.e., given an array of n non-negative integers, tex2html_wrap_inline58363, we wish to find

displaymath58355

The straightforward way of solving this problem is to perform a linear search  of the array. The linear search algorithm is given in Program gif and the running times for the various statements are given in Table gif.

   program493
Program: Linear search to find tex2html_wrap_inline58365

 

 

statement time
3 tex2html_wrap_inline58239
4a tex2html_wrap_inline58181
4b tex2html_wrap_inline58371
4c tex2html_wrap_inline58373
5 tex2html_wrap_inline58375
6 tex2html_wrap_inline58377
7 tex2html_wrap_inline58181
Table: Computing the running time of Program gif

With the exception of line 6, the running times follow simply from Axioms gif, gif and gif. In particular, note that the body of the loop is executed n-1 times. This means that the conditional test on line 5 is executed n-1 times. However, the number of times line 6 is executed depends on the data in the array and not just n.

If we consider that in each iteration of the loop body, the variable result contains the largest array element seen so far, then line 6 will be executed in the tex2html_wrap_inline58387 iteration of the loop only if tex2html_wrap_inline58389 satisfies the following

displaymath58356

Thus, the running time of Program gif, tex2html_wrap_inline58299, is a function not only of the number of elements in the array, n, but also of the actual array values, tex2html_wrap_inline58363. Summing the entries in Table gif we get

displaymath58357

where

eqnarray521

While this result may be correct, it is not terribly useful. In order to determine the running time of the program we need to know the number of elements in the array, n, and we need to know the values of the elements in the array, tex2html_wrap_inline58363. Even if we know these data, it turns out that in order to compute the running time of the algorithm, tex2html_wrap_inline58401, we actually have to solve the original problem!


next up previous contents index

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