SHEN’s CLASS NOTES
Note. We often use variable transformation before solving the relations.
Example 9.
T(n) = 2T(?n?) + lg n.
Setting n = 2k, the above relation becomes
T(2k) = 2T(2k/2) + k.
Let T(n) = S(k), we obtain S(k) = 2S(k/2) + k = ?(klgk).
Then, we have T(n) = ?(klgk) = ?(lg n lglg n).
The summation method and recursion-tree method
The summation method is demonstrated by the following example.
Example 10.
Solve T(n) = 2T(n/2) + nlgn.
21
SHEN’s CLASS NOTES
Solution:
Setting n = 2k, the above relation becomes T(2k) = 2T(2k-1) + k2k Letting W(k) = T(2k), we have W(k) = 2W(k-1) + k2k = 2[2W(k-2) + (k-1)2k-1] + k2k = 22W(k-2) + (k-1)2k + k2k
= 22[2W(k-3) + (k-2)2k-2] + (k-1)2k + k2k = 23W(k-3) + (k-2)2k + (k-1)2k + k2k = ……
= 2k-1W(1) + 2×2k + 3×2k + …+ (k-1)2k + k2k = 2k-1W(1) + 2k [2 + 3 + …+ (k-2) + (k-1) + k] = 2k-1W(1) + 2k [k(k+1)/2 -1] = ?(k22k) = ?(nlg2n).
22
SHEN’s CLASS NOTES
The summation steps can be illustrated by a recursion-tree as follows.
W(k) = 2W(k-1)+k2k
k2k
k2k
W(k-1) W(k-1) (k-1)2k-1
(k-1)2k-1
W(k-2) W(k-2) W(k-2) W(k-2)
(a)
(b)
k2k (c)
k2k
(k-2) recursions (k-1)2k-1
(k-1)2k-1 (k-1)2k (k-2)2k
(k-2)2k-2 (k-2)2k-2 (k-2)2k-2 (k-2)2k-2
W(1) W(1)
???????????(d)
W(1) W(1) ?(2k)
Fig. 1 The construction of recursion tree for W(k) = 2W(k-1) + k2k of Example 10, where (b) and (c) show the first two recursion steps.
23
SHEN’s CLASS NOTES
The Master method
The Master method directly gives the answer to the recurrence relation (1) if the function f(n) satisfies certain conditions.
Theorem 1 (Master Theorem)
Given a recurrence relation T(n) = aT(n/b) + f(n), where a ?1 and b > 0 are two positive constants, the asymptotic bound of T(n) can be obtained in the following cases:
1. If f(n) = O(nlgba??) for some ? > 0,
then T(n) = ?(nlgba). then T(n) = ?(nlgbalgn).
2. If f(n) = ?(nlgba),
3. If f(n) = ?(nlgba??) for some ? > 0, and if af(n/b) ≤ cf(n) for some c < 1 and all n > n0, then T(n) = ?(f(n)).
Proof. See the textbook. Omitted.
24
SHEN’s CLASS NOTES
Example 11
Obtain an asymptotic bound for the following recurrence relations using the master theorem.
(a) T(n) = 9T(n/3) + n (b) T(n) =T(2n/3) +1
(c) T(n) = 3T(n/4) + nlgn.
Solution:
(a) T(n) = 9T(n/3) + n
lgba = lg39 = 2. Set ? = 0.5.
We have f(n) = n = O(n2-0.5)= O(n1.5). Therefore,
T(n) = ? (n2). (b) T(n) =T(2n/3) +1
lgba = lg3/21 = 0.
Since n0 = 1, the first rule in the Master Theorem is not applicable, but second rule can be applied. Therefore,
T(n) = ? (n0lgn) = ? (lgn).
25