Java Reference
In-Depth Information
This logic requires an assignment to
i
,
n
+ 1 comparisons between
i
and
n
,
n
additions to
i
, and
n
more assignments to
i
. In total, the loop-control logic requires
n
+ 1 assignments,
n
+ 1 compari-
sons, and
n
additions. Furthermore, Algorithm A requires for its initialization and loop body
another
n
+ 1 assignments and
n
additions. All together, Algorithm A requires 2
n
+ 2 assignments,
2
n
additions, and
n
+ 1 comparisons.
These various operations probably take different amounts of time to execute. For example, if
each assignment takes no more than
t
=
time units, each addition takes no more than
t
+
time units,
and each comparison takes no more than
t
c
time units, Algorithm A would require no more than
(2
n
+ 2)
t
=
+ (2
n
)
t
+
+ (
n
+ 1)
t
c
time units
If we replace
t
=
,
t
+
, and
t
c
with the largest of the three values and call it
t
, Algorithm A requires no
more than (5
n
+
3)
t
time units. We conclude that Algorithm A requires time directly proportional to
5
n
+
3.
What is important, however, is not the exact count of operations, but the general behavior of
the algorithm. The function 5
n
+
3 is directly proportional to
n
. As you are about to see, we do not
have to count every operation to see that Algorithm A requires time that increases linearly with
n
.
An algorithm's
basic operation
is the most significant contributor to its total time requirement. For
example, Algorithms A and B in Figure 4-1 have addition as their basic operation. An algorithm
that sees whether an array contains a particular object has comparison as its basic operation. Real-
ize that the most frequent operation is not necessarily the basic operation. For example, assign-
ments are often the most frequent operation in an algorithm, but they rarely are basic.
Ignoring operations that are not basic, such as initializations of variables, the operations
that control loops, and so on, will not affect our final conclusion about algorithm speed. For
example, Algorithm A requires
n
additions of
i
to
sum
in the body of the loop. We can conclude
that Algorithm A requires time that increases linearly with
n
, even though we ignored opera-
tions that are not basic to the algorithm.
Whether we look at the number,
n
, of basic operations or the total number of operations, 5
n
+
3,
we can draw the same conclusion: Algorithm A requires time directly proportional to
n
. Thus,
Algorithm A's growth-rate function is
n
.
4.8
Example continued.
Now let's count the number of basic operations required by Algorithms B and
C. The basic operation for Algorithm B is addition; for Algorithm C, the basic operations are addition,
multiplication, and division. Figure 4-2 tabulates the number of basic operations that Algorithms A,
B, and C require. Remember, these counts do not include assignments and the operations that control
the loops. Our discussion in the previous segment should have convinced you that we can ignore these
operations.
FIGURE 4-2
The number of basic operations required by the algorithms in
Figure 4-1
Algorithm A Algorithm B Algorithm C
n
(
n
+
1) / 2 1
Additions
n
Multiplications
1
Divisions
1
(
n
2
+
n
) / 2
Total basic operations
n
3
