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