Java Reference
In-Depth Information
Algorithm B requires time directly proportional to (
n
2
+
n
) / 2, and Algorithm C requires time
that is constant and independent of the value of
n
. Figure 4-3 plots these time requirements as a
function of
n
. You can see from this figure that as
n
grows, Algorithm B requires the most time.
FIGURE 4-3
The number of basic operations required by the algorithms in
Figure 4-1 as a function of
n
Algorithm B:
(
n
2
n
) / 2 operations
Algorithm A:
n
operations
Algorithm C: 3 operations
n
Question 1
For any positive integer
n
, the identity
1
+
2
+
. . .
+
n
=
n
(
n
+
1)
/
2
is one that you will encounter while analyzing algorithms. Can you derive it? If you can, you
will not need to memorize it.
Hint
: Write 1 + 2 + . . . +
n
. Under it write
n
+ (
n
-
1) + . . . + 1.
Then add the terms from left to right.
Question 2
Can you derive the values in Figure 4-2?
Hint
: For Algorithm B, use the iden-
tity given in Question 1.
Note:
Useful identities
1
+
2
+
. . .
+
n
=
n
(
n
+
1)
/
2
1
+
2
+
. . .
+
(
n
-
1)
=
n
(
n
-
1)
/
2
4.9
Typical growth-rate functions are algebraically simple. Why? Recall that since you are not likely to
notice the effect of an inefficient algorithm when the problem is small, you should focus on large
problems. Thus, if we care only about large values of
n
when comparing the algorithms, we can
consider only the dominant term in each growth-rate function.
For example, (
n
2
+
n
) / 2 behaves like
n
2
when
n
is large. First,
n
2
is much larger than
n
for
large values of
n
, so (
n
2
+
n
) / 2 behaves like
n
2
/ 2. Moreover,
n
2
/ 2 behaves like
n
2
when
n
is
large. In other words, for large
n
,
the difference between the value of (
n
2
+
n
) / 2 and that of
n
2
is
relatively small and can be ignored. So instead of using (
n
2
+
n
) / 2 as Algorithm B's growth-rate
