Java Reference
In-Depth Information
644
Unfortunately, the formula
(
n
2
)
T(n) =2T +5n
does not clearly tell us the relationship between n and T(n). To understand the
relationship, let us evaluate T(n/2), using the same formula:
(
n
2
) (
n
4
)
n
2
T =2T +5
Therefore
(
n
4
)
T(n) =2 ¶2T +5n +5n
Let us do that again:
(
n
4
) (
n
8
)
n
4
T =2T +5
hence
(
n
8
)
T(n) =2 ¶2 ¶2T +5n +5n +5n
This generalizes from 2, 4, 8, to arbitrary powers of 2:
(
2
k
)
2
k
T(n) = T
+5nk
Recall that we assume that n=2
m
; hence, for k=m,
(
2
m
)
2
m
T(n) = T
+5nm
=nT(1) +5nm
=n +5n
log
2
(n)
Because n=2
m
, we have m=log
2
(n).
