Recurrence Solving: Review
• T (n) = 2T (n/2) + cn, with T (1) = 1.
• By term expansion.
T (n) = 2T (n/2) + cn
� �
= 2 2T (n/2 ) + cn/2 + cn = 22T (n/22) + 2cn
2
� �
= 2 2T (n/2 ) + cn/2 + 2cn = 23T (n/23) + 3cn
2 3 2
..
= 2iT (n/2i) + icn
• Set i = log2 n. Use T (1) = 1.
• We get T (n) = n + cn(log n) = O(n log n).
Subhash Suri UC Santa Barbara
The Tree View
• T (n) = 2T (n/2) + cn, with T (1) = 1.
Total Cost
T(n)
cn
cn
T(n/2)
T(n/2)
cn/2 2(cn/2) = cn
cn/2
T(n/4) T(n/4) T(n/4) T(n/4)
cn/4 cn/4 cn/4 cn/4 4(cn/4) = cn
T(n/8)
cn/8 8(cn/8) = cn
cn/8 cn/8 cn/8 cn/8 cn/8 cn/8 cn/8
• # leaves = n; # levels = log n.
• Work per level is O(n), so total is O(n log n).
Subhash Suri UC Santa Barbara
Solving By Induction
• Recurrence: T (n) = 2T (n/2) + cn.
• Base case: T (1) = 1.
• Claim: T (n) = cn log n + cn.
T (n) = 2T (n/2) + cn
= 2 (c(n/2) log(n/2) + cn/2) + cn
= cn (log n − 1 + 1) + cn
= cn log n + cn
Subhash Suri UC Santa Barbara
More Examples
• T (n) = 4T (n/2) + cn, T (1) = 1.
Level Work
n 0 cn
n/2 1 4cn/2 = 2cn
n/4 2 16cn/4 = 4cn
n/8 3
i
i 4 cn /2i
i
= 2 cn
Subhash Suri UC Santa Barbara
More Examples
Level Work
n 0 cn
n/2 1 4cn/2 = 2cn
n/4 2 16cn/4 = 4cn
n/8 3
i
i 4 cn /2i
i
= 2 cn
• Stops when n/2i = 1, and i = log n.
• Recurrence solves to T (n) = O(n2).
Subhash Suri UC Santa Barbara
By Term Expansion
T (n) = 4T (n/2) + cn
= 42T (n/22) + 2cn + cn
= 43T (n/23) + 22cn + 2cn + cn
..
� i−1 �
= 4 T (n/2 ) + cn 2
i i
+2 i−2
+ ... + 2 + 1
= 4iT (n/2i) + 2icn
• Terminates when 2i = n, or i = log n.
• 4i = 2i × 2i = n × n = n2.
• T (n) = n2 + cn2 = O(n2).
Subhash Suri UC Santa Barbara
More Examples
√
T (n) = 2T (n/4) + n, T (1) = 1.
√
T (n) = 2T (n/4) + n
� � � √
= 2 2T (n/42) + n/4 + n
√
= 2 T (n/4 ) + 2 n
2 2
� � � √
= 2 2T (n/4 ) + n/4 + 2 n
2 3 2
√
= 2 T (n/4 ) + 3 n
3 3
..
√
= 2 T (n/4 ) + i n
i i
Subhash Suri UC Santa Barbara
More Examples
• Terminates when 4i = n, or when
i = log4 n = log 2n
log 4 = 2 log n.
1
2
1 log n √
T (n) = 2 2 + n log4 n
√
= n(log4 n + 1)
√
= O( n log n)
Subhash Suri UC Santa Barbara
Master Method
�n�
T (n) = aT + f (n)
b
Total Cost
n f(n)
n/b a children af(n/b)
a a
n/b
2 a2 f(n/b2 )
a a a a
ai f(n/bi )
Subhash Suri UC Santa Barbara
Master Method
Total Cost
n f(n)
n/b a children af(n/b)
a a
n/b
2 a2 f(n/b2 )
a a a a
ai f(n/bi )
• # children multiply by factor a at each level.
• Number of leaves is alogb n = nlogb a. Verify by
taking logarithm on both sides.
Subhash Suri UC Santa Barbara
Master Method
• By recursion tree, we get
logb n−1
� �n�
T (n) = Θ(nlogb a) + ai f
i=0
bi
• Let f (n) = Θ(np logk n), where p, k ≥ 0.
• Important: a ≥ 1 and b > 1 are constants.
• Case I: p < logb a.
nlogb a grows faster than f (n).
T (n) = Θ(nlogb a)
Subhash Suri UC Santa Barbara
Master Method
• By recursion tree, we get
logb n−1
� �n�
T (n) = Θ(nlogb a) + ai f
i=0
bi
• Let f (n) = Θ(np logk n), where p, k ≥ 0.
• Case II: p = logb a.
Both terms have same growth rates.
T (n) = Θ(nlogb a logk+1 n)
Subhash Suri UC Santa Barbara
Master Method
• By recursion tree, we get
logb n−1
� �n�
T (n) = Θ(nlogb a) + ai f
i=0
bi
• Let f (n) = Θ(np logk n), where p, k ≥ 0.
• Case III: p > logb a.
nlogb a is slower than f (n).
T (n) = Θ (f (n))
Subhash Suri UC Santa Barbara
Applying Master Method
• Merge Sort: T (n) = 2T (n/2) + Θ(n).
a = b = 2, p = 1, and k = 0. So logb a = 1, and
p = logb a. Case II applies, giving us
T (n) = Θ(n log n)
• Binary Search: T (n) = T (n/2) + Θ(1).
a = 1, b = 2, p = 0, and k = 0. So logb a = 0, and
p = logb a. Case II applies, giving us
T (n) = Θ(log n)
Subhash Suri UC Santa Barbara
Applying Master Method
• T (n) = 2T (n/2) + Θ(n log n).
a = b = 2, p = 1, and k = 1. p = 1 = logb a, and Case
II applies.
T (n) = Θ(n log2 n)
• T (n) = 7T (n/2) + Θ(n2).
a = 7, b = 2, p = 2, and logb 2 = log 7 > 2. Case I
applied, and we get
T (n) = Θ(nlog 7)
Subhash Suri UC Santa Barbara
Applying Master Method
√
• T (n) = 4T (n/2) + Θ(n 2
n).
a = 4, b = 2, p = 2.5, and k = 0. So logb a = 2, and
p > logb a. Case III applies, giving us
√
T (n) = Θ(n n)
2
� �
• T (n) = 2T (n/2) + Θ logn n .
a = 2, b = 2, p = 1. But k = −1, and so the Master
Method does not apply!
Subhash Suri UC Santa Barbara
