Java Reference
In-Depth Information
This analysis gives an intuitive explanation of why the running time is
O
(
N
log
N
) . In general, however, expanding a recursive algorithm to examine
behavior is a bad idea; it violates the third rule of recursion. We next consider
a more formal mathematical treatment.
Let
T
(
N
) represent the time required to solve a maximum contiguous subse-
quence sum problem of size
N
. If
N
= 1, the program takes some constant amount of
time to execute lines 12 to 13, which we call 1 unit. Thus
T
(1) = 1. Otherwise, the
program must perform two recursive calls and the linear work involved in comput-
ing the maximum sum for case 3. The constant overhead is absorbed by the
O
(
N
)
term. How long do the two recursive calls take? Because they solve problems of size
N
/ 2, we know that they must each require
T
(
N
/ 2) units of time; consequently, the
total recursive work is 2
T
(
N
/ 2). This analysis gives the equations
Note that the more
formal analysis
holds for all classes
of algorithms that
recursively solve
two halves and use
linear additional
work.
T
1
()
=
1
TN
()
=
2
TN
/2
(
)
+
ON
()
Of course, for the second equation to make sense,
N
must be a power of 2.
Otherwise, at some point,
N
/ 2 will not be even. A more precise equation is
TN
()
=
TN
/2
(
)
+
TN
/2
(
)
+
ON
()
To simplify the calculations, we assume that
N
is a power of 2 and replace the
O
(
N
) term with
N
. These assumptions are minor and do not affect the Big-Oh
result. Consequently, we need to obtain a closed form solution for
T
(
N
) from
T
1
()
=
1
and
TN
()
=
2
TN
/2
(
)
+
N
(7.6)
This equation is illustrated in Figure 7.21, so we know that the answer
will be
N
log
N
+
N
. We can easily verify the result by examining a few val-
ues:
T
(1),
T
(2) = 4,
T
(4) = 12,
T
(8) = 32, and
T
(16) = 80. We now prove this
analysis mathematically in Theorem 7.4, using two different methods.
figure 7.21
Trace of recursive
calls for recursive
maximum contiguous
subsequence sum
algorithm for
N
= 8
elements
N
N
N
N
Search WWH ::
Custom Search