Java Reference
In-Depth Information
Example14.8
Find the solution for
T(n) = 2T(n=2) + 5n
2
;
T(1) = 7:
For simplicity we assume that n is a power of two, so we will rewrite it as
n = 2
k
. This recurrence can be expanded as follows:
2T(n=2) + 5n
2
T(n)
=
2(2T(n=4) + 5(n=2)
2
) + 5n
2
=
2(2(2T(n=8) + 5(n=4)
2
) + 5(n=2)
2
) + 5n
2
=
2
k
T(1) + 2
k1
5
n
2
k1
2
+ + 2 5
n
2
2
+ 5n
2
:
=
This last expression can best be represented by a summation as follows:
k
X
n
2
=2
i
7n + 5
i=0
7n + 5n
2
k
X
i=0
1=2
i
:
=
From Equation 2.6, we have:
=
7n + 5n
2
2 1=2
k1
7n + 5n
2
(2 2=n)
=
7n + 10n
2
10n
=
10n
2
3n:
=
This is the exact solution to the recurrence for n a power of two. At this
point, we should use a simple induction proof to verify that our solution is
indeed correct.
Example14.9
Our next example models the cost of the algorithm to build
a heap. Recall from Section 5.5 that to build a heap, we first heapify the
two subheaps, then push down the root to its proper position. The cost is:
f(n) 2f(n=2) + 2 log n:
Let us find a closed form solution for this recurrence. We can expand
the recurrence a few times to see that