9.3 Additional Java Operators | 453If an algorithm, from run to run, always takes the same number of steps or fewer, we say that it
executes in an amount of time bounded by a constant. Such algorithms are said to haveconstant
timecomplexity. Be careful:Constant timedoesn’t mean small; it just means that the amount of
work done does not exceed some amount from one run to another regardless of the size of the
problem.
If a loop executes a fixed number of times, the work done is greater than the physical
number of statements but is still constant. What happens if the number of loop iterations can
change from one run to the next? Suppose a data file contains Ndata values to be processed in a
loop. If the loop reads and processes one value during each iteration, then the loop executes N
iterations. The amount of work done therefore depends on a variable, the number of data values.
In this example, the variable Ndetermines the size of the problem.
If we have a loop that executes Ntimes, the number of steps to be executed is some factor
times N. This factor is the number of steps performed within a single iteration of the loop.
Specifically, the work done by an algorithm with a data-dependent loop is given by the
expression
where S 1 is the number of steps in the loop body (a constant for a given simple loop),Nis the
number of iterations (a variable representing the size of the problem), and S 0 is the number of
steps outside the loop. Mathematicians call expressions of this form linear; hence, algorithms
such as this one are said to have linear timecomplexity. Notice that if Ngrows very large, the
term S 1 Ndominates the execution time. That is,S 0 becomes an insignificant part of the total
execution time. For example, if S 0 and S 1 are each 20 steps, and Nis 1,000,000, then the total
number of steps is 20,000,020. The 20 steps contributed by S 0 represent only a tiny fraction of the
total in this case.
What about a data-dependent loop that contains a nested loop? The number of steps in the
inner loop,S 2 , and the number of iterations performed by the inner loop,L, must be multiplied
by the number of iterations in the outer loop:
By itself, the inner loop performs (S 2 L) steps. Because it is repeated Ntimes by the outer loop,
however, it accounts for a total of (S 2 LN) steps. If Lis a constant, then the algorithm still ex-
ecutes in linear time.
(SLN 21 ××) +×(SN) + S 0
Steps performed
by the nested loopSteps performed
by the outer loopSteps performed outside
the outer loopSNS 10 ×+
Steps performed
by the loopSteps performed
outside the loop