Java Reference
In-Depth Information
This form is known as a recurrence with full history. The key to solving such a
recurrence is to cancel out the summation terms. The shifting method for summa-
tions provides a way to do this. Multiply both sides by n and subtract the result
from the formula for nT(n + 1):
n X
= cn 2 + 2
nT(n)
T(k)
k=1
n X
= c(n + 1) 2 + 2
(n + 1)T(n + 1)
T(k):
k=1
Subtracting nT(n) from both sides yields:
= c(n + 1) 2 cn 2 + 2T(n)
(n + 1)T(n + 1) nT(n)
(n + 1)T(n + 1) nT(n)
= c(2n + 1) + 2T(n)
(n + 1)T(n + 1)
= c(2n + 1) + (n + 2)T(n)
c(2n + 1)
n + 1
+ n + 2
T(n + 1)
=
n + 1 T(n):
At this point, we have eliminated the summation and can now use our normal meth-
ods for solving recurrences to get a closed-form solution. Note that c(2n+1)
n+1 < 2c,
so we can simplify the result. Expanding the recurrence, we get
T(n + 1) 2c + n + 2
n + 1 T(n)
2c + n + 2
n + 1
2c + n + 1
n
=
T(n 1)
2c + n + 2
n + 1
2c + n + 1
n
n
n 1 T(n 2)
=
2c +
2c + n + 2
n + 1
4
3 (2c +
3
2 T(1))
=
2c + +
1 + n + 2
n + 1
+ n + 2
n + 1
n + 1
n
+ + n + 2
n + 1
n + 1
n 3
=
2c
2
1
n + 1
1
n + +
1
2
=
2c
1 + (n + 2)
+
=
2c + 2c(n + 2) (H n+1 1)
for H n+1 , the Harmonic Series. From Equation 2.10, H n+1 = (log n), so the
final solution is (n log n).
Search WWH ::




Custom Search