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
 
Search WWH ::




Custom Search