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,
,
we wish to find

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

**Program:** Linear search to find

With the exception of line 6,
the running times follow simply from Axioms , and .
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 iteration of the loop
only if satisfies the following

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

where

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,
.
Even if we know these data,
it turns out that in order to compute the running time of the algorithm,
,
we actually have to solve the original problem!

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