Java Reference
In-Depth Information
We want to compute some estimate of how long it will take a computer to execute this
code. We would like an estimate that does not depend on which computer we use,
either because we do not know which computer we will use or because we might use
several different computers to run the program at different times.
One possibility is to count the number of “steps,” but it is not easy to decide what a
step is. In this situation the normal thing to do is count the number of
operations
. The
term
operations
is almost as vague as the term
step
, but there is at least some agreement in
practice about what qualifies as an operation. Let us say that, for this Java code, each
application of any of the following will count as an operation:
=
,
<
,
&&
,
!
,
[]
,
==
, and
++
.
The computer must do other things besides carry out these operations, but these seem to
be the main things that it is doing, and we will assume that they account for the bulk of
the time needed to run this code. In fact, our analysis of time will assume that everything
else takes no time at all and that the total time for our program to run is equal to the
time needed to perform these operations. Although this is an idealization that clearly is
not completely true, it turns out that this simplifying assumption works well in practice,
and so it is often made when analyzing a program or algorithm.
Even with our simplifying assumption, we still must consider two cases: Either the
value
target
is in the array or it is not. Let us first consider the case when
target
is not
in the array. The number of operations performed will depend on the number of array
elements searched. The operation
=
is performed two times before the loop is executed.
Since we are assuming that
target
is not in the array, the loop will be executed
N
times,
one for each element of the array. Each time the loop is executed, the following opera-
tions are performed:
<
,
&&
,
!
,
[]
,
==
, and
++
. This adds five operations for each of
N
loop
iterations. Finally, after
N
iterations, the Boolean expression is again checked and found
to be
false
. This adds a final three operations (
<
,
&&
,
!
).
3
If we tally all these operations,
we get a total of 6
N
+
5 operations when the target is not in the array. We will leave it as
an exercise for the reader to confirm that if the target is in the array, then the number of
operations will be 6
N
+
5
or less
. Thus, the worst-case running time is
T
(
N
) = 6
N
+
5
operations for any array of
N
elements and any value of
target
.
We just determined that the worst-case running time for our search code is 6
N
+
5
operations. But an operation is not a traditional unit of time, like a nanosecond, second,
or minute. If we want to know how long the algorithm will take on some particular
computer, we must know how long it takes that computer to perform one operation. If
an operation can be performed in one nanosecond, then the time will be 6
N
+
5 nano-
seconds. If an operation can be performed in one second, the time will be 6
N
+
5 sec-
onds. If we use a slow computer that takes ten seconds to perform an operation, the
time will be 60
N
+
50 seconds. In general, if it takes the computer
c
nanoseconds
to perform one operation, then the actual running time will be approximately
3
Because of short-circuit evaluation,
!(found)
is not evaluated, so we actually get two, not
three, operations. However, the important thing is to obtain a good upper bound. If we
add in one extra operation, that is not significant.
