Java Reference
In-Depth Information
function, we can use
n
2
—the term with the largest exponent—and say that Algorithm B requires
time proportional to
n
2
. On the other hand, Algorithm C requires time that is independent of
n
, and
we saw earlier that Algorithm A requires time proportional to
n
. We conclude that Algorithm C is
the fastest and Algorithm B is the slowest.
Note:
The relative magnitudes of common growth-rate functions
The growth-rate functions that you are likely to encounter grow in magnitude as follows
when
n
>
10:
1
<
log(log
n
)
<
log
n
<
log
2
n
<
n
<
n
log
n
<
n
2
<
n
3
<
2
n
<
n
!
The logarithms given here are base 2. As you will see later in Segment 4.16, the choice of
base does not matter.
Figure 4-4 tabulates the magnitudes of these functions for increasing values of the prob-
lem size
n
. From this data you can see that algorithms whose growth-rate functions are log(log
n
), log
n
, or log
2
n
take much less time than algorithms whose growth-rate function is
n
.
Although the value of
n
log
n
is significantly larger than
n
, either of those functions describes
a growth rate that is markedly faster than
n
2
.
FIGURE 4-4
Typical growth-rate functions evaluated at increasing values of
n
n
log(log
n
) log
n
log
2
n
n
2
n
3
2
n
n
n
log
n
n
!
10
2
10
3
10
3
10
5
10
2
3
11
10
33
10
2
10
4
10
6
10
30
10
94
3
7
44
100
664
10
3
10
6
10
9
10
301
10
1435
3
10
99
1000
9966
10
4
10
8
10
12
10
3010
10
19,335
4
13
177
10,000
132,877
10
5
10
10
10
15
10
30,103
10
243,338
4
17
276
100,000
1,660,964
10
6
10
12
10
18
10
301,030
10
2,933,369
4
20
397
1,000,000
19,931,569
Note:
When analyzing the time efficiency of an algorithm, consider large problems. For
small problems, the difference between the execution times of two solutions to the same
problem is usually insignificant.
For some algorithms that operate on a data set, the execution time depends only on the size of the
data set. For example, the time needed to find the smallest integer in an array of integers depends
only on the number of integers, not on the integers themselves. Finding the smallest of 100 integers
takes the same amount of time regardless of the values of the integers.
Other algorithms, however, have time requirements that depend not only on the size of the data
set, but also on the data itself. For example, imagine that an array contains a certain value, and we
want to know where in the array it occurs. Suppose our search algorithm examines each value in
the array until it finds the desired one. If the algorithm finds this desired value in the first array ele-
ment it examines, it makes only one comparison. In this
best case
, the algorithm takes the least
