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