Java Reference
In-Depth Information
the algorithm as a function of n, written as T(n). We will always assume
T(n) is a non-negative value.
Let us call c the amount of time required to compare two integers in
function
largest
. We do not care right now what the precise value of c
might be. Nor are we concerned with the time required to increment vari-
able i because this must be done for each value in the array, or the time
for the actual assignment when a larger value is found, or the little bit of
extra time taken to initialize
currlarge
. We just want a reasonable ap-
proximation for the time taken to execute the algorithm. The total time
to run
largest
is therefore approximately cn, because we must make n
comparisons, with each comparison costing c time. We say that function
largest
(and by extension ,the largest-value sequential search algorithm
for any typical implementation) has a running time expressed by the equa-
tion
T(n) = cn:
This equation describes the growth rate for the running time of the largest-
value sequential search algorithm.
Example3.2
The running time of a statement that assigns the first value
of an integer array to a variable is simply the time required to copy the value
of the first array value. We can assume this assignment takes a constant
amount of time regardless of the value. Let us call c
1
the amount of time
necessary to copy an integer. No matter how large the array on a typical
computer (given reasonable conditions for memory and array size), the time
to copy the value from the first position of the array is always c
1
. Thus, the
equation for this algorithm is simply
T(n) = c
1
;
indicating that the size of the input n has no effect on the running time.
This is called a constant running time.
Example3.3
Consider the following code:
sum=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
sum++;
What is the running time for this code fragment? Clearly it takes longer
to run when n is larger. The basic operation in this example is the increment
