Data Structures and Algorithms
Recursion Tree and Master’s Method
Indian Institute of Information Technology Sri City, India
1, 𝑛 = 0
• Example-2: Show that the solution of 𝑇(𝑛) = ቊ
𝑇(𝑛 − 1) + 1, 𝑛 > 0
is O(n2) using substitution method.
The recursion-tree method for solving
recurrences
• Problem with Substitution method: coming up with a good guess
• Drawing out a recursion tree, serves as a straightforward way to
devise a good guess.
• In a recursion tree, each node represents the cost of a single
subproblem somewhere in the set of recursive function invocations.
• We sum the costs within each level of the tree to obtain a set of per-
level costs, and then we sum all the per-level costs to determine the
total cost of all levels of the recursion.
Example-1: Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
L1.4
Example-1: Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
T(n)
L1.5
Example-1: Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
T(n/2) T(n/2)
L1.6
Example-1: Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2 cn/2
T(n/4) T(n/4) T(n/4) T(n/4)
L1.7
Example-1: Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2 cn/2
cn/4 cn/4 cn/4 cn/4
Θ(1)
L1.8
Example-1: Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2 cn/2
h = lg n
cn/4 cn/4 cn/4 cn/4
Θ(1)
L1.9
Example-1: Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2
h = lg n
cn/4 cn/4 cn/4 cn/4
Θ(1)
L1.10
Example-1: Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2 cn
h = lg n
cn/4 cn/4 cn/4 cn/4
Θ(1)
L1.11
Example-1: Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2 cn
h = lg n
cn/4 cn/4 cn/4 cn/4 cn
…
Θ(1)
L1.12
Example-1: Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2 cn
h = lg n
cn/4 cn/4 cn/4 cn/4 cn
…
Θ(1) #leaves = n Θ(n)
L1.13
Example-1: Recursion tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn cn
cn/2 cn/2 cn
h = lg n
cn/4 cn/4 cn/4 cn/4 cn
…
Θ(1) #leaves = n Θ(n)
Total = Θ(n lg n)
L1.14
Example-2: Recursion tree
Solve T (N ) = 3T (N/4) + cn2, where c > 0 is constant.
L1.15
Example-2: Recursion tree
Solve T (N ) = 3T (N/4) + cn2, where c > 0 is constant.
Here the cost at each level is different
By solving as the sum of as a GP, the RHS becomes
16
Example-2: Recursion tree
Solve T (N ) = 3T (N/4) + cn2, where c > 0 is constant.
An upper bound can be obtained by assuming the series as infinite
This means that the complexity is in O(n^2)
17
The master method for solving recurrences
• The master method provides a “cookbook” method for solving recurrences of the
form
• where a>=1 and b>1 are constants and f (n) is an asymptotically positive
function.
• Then, T(n) has following asymptotic bounds according to Master Theorem.
• Example-1: consider
• For this recurrence, we have a a=9, b=3, f (n) = n, and thus we have
that Since we can apply case 1 of the
master theorem and conclude that the solution is T(n) = Ө (n)
• Example-2: Consider
