Recursive
Functions II
Recursive Functions - Recap
Example 1:
• T(n) = 2T(n/2) + n; T(n) = Θ(n log n)
Example 2:
• T(n) = 2T(n/2) + n2; T(n) = Θ(n2)
Example 3:
• T(n) = 4T(n/2) + n; T(n) = Θ(n2)
2
Master Theorem
Generalized Recursive Function:
• T(n) = aT(n/b) + cnk
a>=1, b>1, k>0
Growth of T(n) will be determined by
relative values of k and log ba
3
Master Theorem
T(n) = aT(n/b) + cnk
Case I: k = log ba
• T(n) = Θ(nk log n)
Case II: k > log ba
• T(n) = Θ(nk)
Case II: k < log ba
• T(n) = Θ(nlog ba)
4
Master Theorem
Formal Definition
T(n) = aT(n/b) + f(n)
If f(n) = Θ(nlog ba), then
T(n) = Θ(f(n) log n)
If f(n) = Ω(nlog ba+ε) and af(n/b)<=cf(n),
T(n) = Θ(f(n))
If f(n) = O(nlog ba-ε), then
T(n) = Θ(nlog ba)
5
Master Theorem
T(n)= aT(n/b) + cnk
Example 1: T(n) = 2T(n/2) + n
• k = 1, logba = log22 = 1; Case I
Example 2: T(n) = 2T(n/2) + n2
• k = 2, logba = log22 = 1; Case II
Example 3: T(n) = 4T(n/2) + n
• k = 1, logba = log24 = 2; Case III
6
Examples
1. T(n) = 8T(n/2) + n
2. T(n) = T(n/2) + 1
3. T(n) = 3T(n/5) + 4n2
4. T(n) = T(n/2) + T(n/4) + n2
7
Recursion Tree 1
T(n) = T(n/2) + T(n/4) + cn2
T(n) cn2
8
Recursion Tree 1
T(n) = T(n/2) + T(n/4) + cn2
T(n) cn2
T(n/2) T(n/4) c((n/2)2+(n/4)2)
9
Recursion Tree 1
T(n) = T(n/2) + T(n/4) + cn2
T(n) cn2
T(n/2) T(n/4) c((n/2)2+(n/4)2)
T(n/4) T(n/8) T(n/8) T(n/16) c((n/4)2+2(n/
8)2+ (n/16)2)
10
Recursion Tree 1
T(n) = T(n/2) + T(n/4) + cn2
T(n) cn2
T(n/2) T(n/2) c((n/2)2+(n/4)2)
T(n/4) T(n/8) T(n/8) T(n/16) c((n/4)2+2(n/
8)2+ (n/16)2)
T(n/8) T(n/16) T(n/16) T(n/32) c(?)
T(n/16) T(n/32) T(n/32) T(n/64)
11
Analysis of Recursive Tree 1
Total Number of operations:
T(n) = c (n2 + 5n2/16 + 25n2/256 + …)
Thisis a decreasing series in n2
Hence, T(n) = O(n2)
12
Recursion Tree 2
T(n) = T(n/4) + T(3n/4) + cn
T(n) cn
13
Recursion Tree 2
T(n) = T(n/4) + T(3n/4) + cn
T(n) cn
T(n/4) T(3n/4) c(n/4+3n/4)
T(3n/16) T(9n/16)
T(n/16) T(3n/16) c(n/16+6n/
16+9n/16)
14
Recursion Tree 2
T(n) = T(n/4) + T(3n/4) + cn
T(n) cn
T(n/4) T(3n/4) c(n/4+3n/4)
T(3n/16) T(9n/16)
T(n/16) T(3n/16) c(n/16+6n/
16+9n/16)
T(n/64) c(?)
T(3n/64) T(3n/64)T(9n/64) T(9n/64) T(27n/64)
15
Analysis of Recursive Tree 2
Total Number of operations:
T(n) = c(n + n + n+ …)
T(n) = O(n log n)
16
Recursion Tree 3
T(n) = T(n-a) + T(a) + cn
T(n) cn
17
Recursion Tree 3
T(n) = T(n-a) + T(a) + cn
T(n) cn
T(n-a) T(a) c(n-a+a)
18
Recursion Tree 3
T(n) = T(n-a) + T(a) + cn
T(n) cn
T(n-a) T(a) c(n-a+a)
T(n-2a) T(a)
c(n-2a+a)
T(n-3a) T(a)
c(n-3a+a)
19
Recursion Tree 3
T(n) = T(n-a) + T(a) + cn
T(n) cn
T(n-a) T(a) c(n-a+a)
T(n-2a) T(a)
c(n-2a+a)
T(n-3a) T(a)
c(n-3a+a)
.....
T(n-ha) T(a) Assumption c(a)
n=ha
20
Analysis of Recursive Tree 3
Total Number of operations:
T(n) = c(2n+(n-a)+(n-2a)+(n-3a)+ …+a)
=c(2n+(n-a)+(n-2a)+(n-3a)+…+(n-(h-
1)a+a)
21
Analysis of Recursive Tree 3
Total Number of operations:
T(n) = c(2n+(n-a)+(n-2a)+(n-3a)+ …+a)
=c(2n+(n-a)+(n-2a)+(n-3a)+…+(n-(h-
1)a+a)
= c((h+2)n - (h(h-1)a/2a)
= c(((n/a)+2)n – (n/a)(n/a-1))a/2))
as h=n/a
≈ c((n2/a – n2/a …))
22
Analysis of Recursive Tree 3
Total Number of operations:
T(n) = c(2n+(n-a)+(n-2a)+(n-3a)+ …+a)
=c(2n+(n-a)+(n-2a)+(n-3a)+…+(n-(h-
1)a+a)
= c((h+2)n - (h(h-1)a/2a)
= c(((n/a)+2)n – (n/a)(n/a-1))a/2))
as h=n/a
≈ c((n2/a – n2/a …))
Hence, T(n) = O(n2)
23
The End
24
