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).