Java Reference
In-Depth Information
Assuming that N is a power of 2 , the solution to the equation T ( N ) = 2 T ( N /2) + N ,
with initial condition T (1) = 1 , is T ( N ) = N log N + N .
Theorem 7.4
Proof
(Method 1)
For sufficiently large N , we have T ( N / 2) = 2 T ( N / 4) + N /2 because we can use Equa-
tion 7.6 with N /2 instead of N . Consequently, we have
2 T ( N / 2) = 4 T ( N / 4) + N
Substituting this into Equation 7.6 yields
(7.7)
T ()
=
4 TN /4
(
)
+
2 N
If we use Equation 7.6 for
N 4
and multiply by 4 , we obtain
4 TN /4
(
)
=
8 TN /8
(
)
+
N
which we can substitute into the right-hand side of Equation 7.7 to obtain
T ()
=
8 TN /8
(
)
+
3 N
Continuing in this manner, we obtain
2 k TN /2 k
T ()
=
(
)
+
kN
Finally, using
k
=
log
N
(which makes sense, because then
2 k
=
N
), we obtain
T ()
=
NT () NN
+
log
=
NNN
log
+
Although this proof method appears to work well, it can be difficult to
apply in more complicated cases because it tends to give very long equations.
Following is a second method that appears to be easier because it generates
equations vertically that are more easily manipulated.
Proof of
Theorem 7.4
(Method 2)
We divide Equation 7.6 by N , yielding a new basic equation:
T ()
N
TN /2
(
)
=
+
1
------------
------------------
N /2
This equation is now valid for any N that is a power of 2 , so we may also write the fol-
lowing equations:
(continued on next page)
Search WWH ::




Custom Search