Chapter 4  Recursion Tree 
Document last modified: 
Uses:
Use recursion tree to determine a good asymptotic bound on the recurrence T(n) = …
Sum the costs within each level of the tree to obtain a set of perlevel costs.
Sum all the perlevel costs to determine the total
cost of all levels of recursion.
Best if used to generate a good guess for the closed
form bounds of the recurrence T(n).
Guess is verified by using Substitution Method or Master Method.
Note: the bound sought will be one of the following:
 “asymptotic upper bound” means you’re looking for BigO
 “tight asymptotic bound” means you’re looking for Θ
 “asymptotic lower bound” means you’re looking for Ω
Steps:
Draw the tree based on the recurrence
From the tree determine:
# of levels in the tree
cost per level
# of nodes in the last level
cost of the last level (which is based on the number found in 2c)
Write down the summation using ∑ notation – this summation sums up the cost of all the levels in the recursion tree
Recognize the sum or look for a closed form solution for the summation created in 3). Use Appendix A.
Apply that closed form solution to your summation coming up with your “guess” in terms of BigO, or Θ, or Ω (depending on which type of asymptotic bound is being sought).
Then use Substitution Method or Master Method to prove that the bound is correct.
Example  Show Factorial is O(n)
For the recursive n! algorithm:
int F(int n) { if (n == 1) return 1;
return F (n1) * n;
}n! is defined by the recurrence:
F(1) = 1 for n=1 F(n) = F(n1)*n for n>1
The run time cost, T(n), is defined by the recurrence:
T(1) = 1 for n=1 T(n) = T(n1) + 1 for all n>1
where 1 is the running time for each execution of the factorial function.
Backward Substitution method for exact closedend equation  T(n) = n
T(n) = T(n1) + 1 = [ T(n2)+1 ] + 1 Substitute T(n2)+1 for T(n1) = T(n2) + 2 = [ T(n3)+1 ] + 2 Substitute T(n3)+1 for T(n2) = T(n3) + 3 = [ T(n4)+1 ] + 3 Substitute T(n4)+1 for T(n3) = T(n4) + 4
After i substitutions:
T(n) = T(ni) + T(ni+1) + ... + 1 + 1
Initial condition: T(1) = T(ni)
ni=1 or i = n1
T(1) = T(ni) + i
= T(1) + n1
= 1 + 0 = 1
Closedend formula:
T(n) = T(1) + n1 = 1 + n1 = n
Prove by induction:
T(n) = T(n1)+1 = n
Base: T(1) = 1 by recurrence definition
T(2) = T(21) + 1 = T(1) + 1 = 2IH: T(k) = k
Show: T(k+1) = k+1
T(k+1) = T((k+1)1) + 1 Recurrence definition = T(k) + 1 = k + 1 IH: T(k) = k Guess method using Recursion Tree  T(n) = n
T(1) = 1 for n=1 T(n) = T(n1) + 1 for all n>1
Problem size 4
Level Problem Cost 0 T(4)
→ 1 1 T(3)
→ 1 2 T(2)
→ 1 3 T(1) → 1 Total 4 Height 3
Levels 4
Problem size n
Level Problem Cost 0 T(n)
→ 1 1 T(n1)
→ 1 2 T(n2)
→ 1 : : n1 T(1) → 1 Total n Height n1
Levels n
Backward substitution gave exact solution of: T(n) = n
Recursion tree provides guess: T(n) = n = O(n)
Guess is sum of costs at each level.
T( n ) = 1 + 1 + ... + 1 = n
Show: T(n) = O(n)
By definition of BigO:
0 ≤ T(n) ≤ cn must hold
For O(n) must prove: 0 ≤ T(n) ≤ cn for c > 0, for all n ≥ n_{0}
Inductive Hypothesis:
T(k1) ≤ c(k1)
Show:
T(k) = T(k1) + 1 ≤ ck
T(k) = T(k1) + 1 Recurrence ≤ c(k1) + 1 Substitute IH = ck  c + 1 ≤ ck Solve ck  c + 1 ≤ ck c + 1 ≤ 0 c ≤ 1 c ≥ 1 Base or boundary conditions: Now find c and n_{0} to satisfy O definition
Verify: T_{R}(n) ≤ T_{C}(n) Recurrence ≤ Closedend
T_{R}(n) = T_{R}(n1) + 1 Recurrence
T_{C}(n) = cn Closedend bounds solution for O(n)


O(n): 0 ≤ T(n) ≤ cn for c ≥ 1, for all n ≥ n_{0 }= 1 or 2
Example Recursion Tree  Finding O
T(1) = 5 n=1 T(n) = 2T(n1) + 3 n>1 
Problem size 4
Height 3 Levels 4 
n=4 a) # levels = n

Problem size 4
n=4

Recursion tree provides guess: T(n) = O(2^{n})
T(n) = 3(2^{n1}1) + 5*2^{n1}
Show: T(n) = O(2^{n})
By definition of BigO:
T(n) = 2T(n1) + 3 ≤ c2^{n} must hold
Show:
T(n) = 2T(n1) + 3 ≤ c2^{n}
Inductive Hypothesis:
T(n1) ≤ c(2^{n1})
T(n) = 2T(n1) + 3 Recurrence ≤ 2c(2^{n1}) + 3 Substitute IH = c2^{n} + 3 ≤ c2^{n} Fails Substitution Subtlety
Show:
T(n) = 2T(n1) + 3 ≤ c2^{n}  b
Inductive Hypothesis:
T(n1) ≤ c(2^{n1})  b
T(n) = 2T(n1) + 3 Recurrence ≤ 2[c(2^{n1})  b] + 3 Substitute IH = c2^{n} 2b + 3 ≤ c2^{n}  b Solve c2^{n} 2b + 3 ≤ c2^{n}  b 3 ≤ b Base or boundary conditions: Now find c and n_{0} to satisfy O definition
T(1) = 5 n=1 T(n) = 2T(n1) + 3 n>1
Verify: T_{R}(n) ≤ T_{C}(n) Recurrence ≤ Closedend
T_{R}(n) = 2T_{R}(n1) + 3 Recurrence
T_{C}(n) = c2^{n}  b Closedend bounds solution for O(2^{n})
Try n_{0} = 2
T_{R}(n) ≤ T_{C}(n) T_{R}( 2 ) ≤ T_{C}( 2 ) 2T_{R}( 21 ) + 3 ≤ T_{C}( 2 ) Substitute 2T( 1 ) + 3 ≤ c2^{2}  b T( 1 ) = 5 10 + 3 ≤ 4c  3 Let b = 3 13 ≤ 4c 3 16 ≤ 4c c ≥ 4 Succeeds for n_{0} = 2
O(n): T(n) ≤ c2^{n}  b ≤ c2^{n} for c ≥ 4, ∀n ≥ n_{0 }= 2
Question 4.12.1
 5 if n = 1
T(n) = 
 3T(n1) + 2 if n > 1Draw the 0, 1 and 2 levels of the recursion tree showing the size in terms of n and the cost of each node.
Determine the number of nodes and cost at each level.
Determine the total cost for all levels (i.e. in summation form).
Example
The run time cost of f(n) is defined by the recurrence, T(n):
f(n)
if n == 1 return // Cost 6
else // Cost 5
f(n/2)
f(n/2)
f(n/2)
f(n/2)
returnT(1) = 6 for n=1 T(n) = 4T(n/2) + 5 for all n>1
n = 8 generates the following partial recursion tree and cost:
Level Nodes Cost 0 4^{0}=1 5 = 4^{0}*5
1 4^{1}=4 20 = 4^{1}*5
2 4^{2}=16 90 = 4^{2}*5
3 4^{3}=64 384 = 4^{3}*6 lg 8 = 3Cost for Level 0 through lg n1:
for n = 8: 5 * (8^{2}1)/3 = 5 * 21 = 105
Cost for Level lg n: 6 * 4^{lg n} = 6 * n^{lg 4} = 6 * n^{2}
for n = 8: 6 * 4^{lg 8} = 6 * 64 = 384
Total cost:
for n = 8: 105 + 384 = 489
O(n^{2}) Guess: 5 * (n^{2}1)/3 + 6 * n^{2}
Example
The run time cost of f(n) is defined by the recurrence, T(n):
f(n)
if n == 1 return // Cost 6
else // Cost n
f(n/2)
f(n/2)
f(n/2)
f(n/2)
for(i=1; i<=n; i++) print i;
returnT(1) = 6 for n=1 T(n) = 4T(n/2) + n for all n>1
n = 8 generates the following partial recursion tree and cost:
Level Nodes Cost 0 4^{0}=1 8 = 4^{0}*n/2^{0} = (4/2)^{0}*n
1 4^{1}=4 16 = 4^{1}*n/2^{1} = (4/2)^{1}*n
2 4^{2}=16 32 = 4^{2}*n/2^{2} = (4/2)^{2}*n
3 4^{3}=64 384 = 4^{3}*6Cost for Level 0 through lg n1:
for n = 8: (8^{2}8) = 56
Cost for Level lg n: 6 * 4^{lg n} = 6 * n^{lg 4} = 6 * n^{2}
for n = 8: 6 * 4^{lg 8} = 6 * 64 = 384
Total cost:
for n = 8: 56 + 384 = 440
O(n^{2}) Guess: (n^{2}n) + 6 * n^{2} = 7n^{2 } n
Example
The run time cost of f(n) is defined by the recurrence, T(n):
f(n)
if n == 1 return // Cost T(1)
else // Cost n^{2}
f(n/3)
f(n/3)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++) print i*j;
returnT(n) = 2T(n/3) + n^{2} for all n>1
n = 27 generates the following partial recursion tree and cost:
: : : :
T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1)
: : : :
T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1)
Level Nodes Cost
0 2^{0}=1 2^{0}*(n/3^{0})^{2 }= (2/3^{2})^{0}*n^{2}
1 2^{1}=2 2^{1}*(n/3^{1})^{2 }= (2/3^{2})^{1}*n^{2}
2 2^{2}=4 2^{2}*(n/3^{2})^{2 }= (2/3^{2})^{2}*n^{2}3 2^{3}=8 2^{3}*(n/3^{3})^{2 }= (2/3^{2})^{3}*n^{2 } : : :
log_{3}n 2^{log}_{3}^{n} T(1)*2^{log}_{3}^{n} = T(1)*n^{log}_{3}^{2}
Cost for Level 0 through log_{3} n1:
Cost for bottom, Level log_{3} n
Total cost:
Equation A.5
Example  Merge Sort  Finding O
Recall that a balanced binary tree of height k has k + 1 levels. We've proven that.
A problem of size n=16 divided as described by the following recurrence equation would then be represented by the tree at right.
 O(1) if n = 1
T(n) = 
 2T(n/2) + O(n) if n > 1Use the implied coefficient c for arithmetic purposes:
 c if n = 1
T(n) = 
 2T(n/2) + cn if n > 1
Steps using recursion tree.
 Draw the tree based on the recurrence. Recursion tree shows successive expansions of the recurrence.
Root cost = cn

For each of size n/2 subproblems, cost:


Each level cost sums to cn, for example: cn = cn/2 + cn/2 Continue expanding tree until problem sizes are 1, each with a cost of c cn = c + c + ... + c
Height = lg n Levels = lg n + 1 Cost/level = cn Bottom node number n = 2^{lg n} for height lg n dividing problem by 2 each time.
Bottom cost = T(1) * n = cn Note that T(1) is problem size n=1, there are n subproblems at bottom. 
Question 4.12.2  Draw the recursion tree.
 c if n = 1
T(n) = 
 4T(⌊n/2⌋) + cn if n > 1Can ignore ⌊ ⌋ by simplifying assumption that n is a power of 2.
Steps using recursion tree continued.

Example  Merge Sort  Find O
The following is a Merge_Sort that divides each problem into 3 subproblems
Merge_Sort (A, p, r) 1 if p < r then 2 q ← floor ((p + r) / 3) 3 Merge_Sort (A, p, q) 4 Merge_Sort (A, q + 1, 2*q) 5 Merge_Sort (A, 2*q + 1, r) 6 Merge (A, p, q, 2*q, r) yielding the following recurrence:
 b if n = 1
T(n) = 
 3T(n/3) + bn if n > 1where bn is the cost to divide and the combine cost of Merge.
Recursion Tree
Diagram recursion tree to generate a guess at a closed form bounds for: T(n) = 3T(n/3) + bn
Height: log_{3}n
Levels: log_{3}n + 1
Cost per level: bn
Bottom (size n=1 problem):
Cost per node: b
Nodes: 3^{log}_{3}^{n} = n
3  the number of subproblems created each recurrence (level)
log_{3}n  the number of recurrences (levels preceding bottom)
O(n log_{3}n): 0 ≤ T(n) ≤ cn log_{3}n
Recurrence:
 b if n = 1
T(n) = 
 3T(n/3) + bn if n > 1Guess: T(n) = bn log_{3}n + bn = O(n log_{3}n)
Basis:
T(1) = 3T(1/3) + b*1 = b ≤ cn log_{3}n = c1 log_{3} 1 = 0 at odds with T(1) = b and b > 0
Need to establish inductive basis for n ≥ n_{0} for n_{0} of our choosing:
Choose n_{0}=3
Use as inductive basis (not the recurrence basis which is T(1)=b):
T(3) ≤ c3 log_{3}3 = 3c
Prove basis holds for n_{0}
By the recurrence: T(n) = 3T(n/3) + bn
T(3) = 3T(3/3) + 3b = T(1) + T(1) + T(1) + 3b = b + b + b + 3b = 6b Need 6b = T(3) ≤ c3 log_{3}3 = 3c 6b ≤ 3c
2b ≤ c
so let c_{ }= 2b IH: Assume holds for n/3, that is:
T(n/3) ≤ c(n/3) log_{3}(n/3) is true
Show: T(n) ≤ cn log_{3}n
T(n) = 3T(n/3) + bn Recurrence ≤ 3[c(n/3) log_{3}(n/3)] + bn IH substitution = 3[c(n/3) log_{3}n  c(n/3) log_{3}3] + bn Recall that log a/b = log a  log b = 3[c(n/3) log_{3}n  c(n/3)] + bn log_{3}3=1 = 3c(n/3) log_{3}n  3c(n/3) + bn = cn log_{3}n  cn + bn ≤ cn log_{3}n cn log_{3}n  cn + bn ≤ cn log_{3}n
cn + bn ≤ 0
c + b ≤ 0
b ≤ c, that is c ≥ b
Note that c can be chosen while b is determined by algorithm.
Recall to satisfy the induction basis we have already chosen
c = 2b ≥ b
Therefore:
T(n) = O(n log_{3}n) for c = 2b and n_{0}=3
Question 4.13  For:
 c if n = 1
T(n) = 
 4T(⌊n/2⌋) + cn if n > 1
 From the tree determine:
 # of levels in the tree of height lg n:
 cost per level:
 # of nodes in the last level, problem size n=1:
 cost of the last level (which is based on the number found in 2c times base cost):
 Write down the summation using ∑ notation. Summation of cost for lg n levels in the recursion tree + bottom level.
 Find closed form solution for the summation created in 3) often using Appendix A.
 Use closed form solution as “guess” in terms of BigO, or Θ, or Ω (depending on which type of asymptotic bound is being sought).
T(n) = O( ? )  Then use Substitution Method or Master Method to prove that the bound is correct.
See Question 4.10 and 4.11 for Substitution Method.
Example  Unbalanced Recursion Tree  Find Θ
T(n) = T(n/3) + T(2n/3) + Θ(n)
O upper bound: rewrite as T(n) ≤ T(n/3) + T(2n/3) + cn
Ω lower bound: rewrite as T(n) ≥ T(n/3) + T(2n/3) + cn
By summing across each level, the recursion tree shows the cost at each level of recursion (minus the costs of recursive calls, which appear in subtrees):
 There are log_{3}n full levels,
after log_{3/2}n levels, the problem size is down to 1;
log_{3}n ≤ log_{3/2}n
 Height log_{3/2}n
 Recall that dividing n = 2^{i} size problem into 1/2 size problems has a tree height:
lg n = log_{2/1}n = log_{2/1}(2/1)^{i}=log_{2}2^{i} = i
 T(2n/3) means that the n size problem is reduced to 2/3 the size but double the size of T(n/3).
 T(2n/3) path is the longest from root to leaf.
 A leaf is a problem of size 1.
 The longest path is then: n → (2/3)n → (2/3)^{2}n → ... → 1
 (2/3)^{k}n=1 when k=log_{3/2} n the height is log_{3/2} n
 Solve for k in (2/3)^{k}n=1
 n = (3/2)^{k}
 log_{3/2}n=log_{3/2}3/2^{k}=k
 Cost ≤ cn log_{3/2}n
 Expect cost to be at most: # levels * cost at each level = cn log_{3/2}n when total cost evenly distributed across all levels.
 Because some internal leaves are absent (more absent nearer bottom), some levels contributes ≤ cn.
 A complete binary tree of height log_{2}n has 2^{log}_{2}^{n} = n^{log}_{2}^{2} = n leaves (at bottom).
 The complete binary tree leaves are: 2^{log}_{3/2}^{n} = n^{log}_{3/2}^{2 }
 Upper bound guess: dn log_{3/2} n = O(n lg n) for some positive constant d.
 Note: log_{3/2} n/log_{2} n= (log_{2} n*log_{3/2} 2)/ log_{2} n = log_{3/2} 2 = 0.585
 n log_{3/2} n / n lg n = c or about 0.585 suggesting dn log_{3/2} n = O(n lg n)
O upper bound: rewrite as T(n) ≤ T(n/3) + T(2n/3) + cn
Guess: T(n) = O(n lg n)
IH: T(n/3) ≤ d(n/3) lg(n/3)
T(2n/3) ≤ d(2n/3) lg(2n/3)
Substitution: Recall: log a/b = log a  log b
T(n) ≤ T(n/3) + T(2n/3) + cn ≤ d(n/3) lg(n/3) + d(2n/3) lg(2n/3) + cn IH = (d(n/3) lg n − d(n/3) lg 3) + (d(2n/3) lg n − d(2n/3) lg(3/2)) + cn = dn lg n − d((n/3) lg 3 + (2n/3) lg(3/2)) + cn = dn lg n − d((n/3) lg 3 + (2n/3) lg 3 − (2n/3) lg 2) + cn = dn lg n − dn(lg 3 − 2/3) + cn ≤ dn lg n if −dn(lg 3 − 2/3) + cn ≤ 0 , d ≥ c / (lg 3 − 2/3)
Therefore, T(n) = O(n lg n).
Ω lower bound: rewrite as T(n) ≥ T(n/3) + T(2n/3) + cn
Guess: T(n) ≥ dn lg n.
Substitution: Same as for the upper bound, but replacing ≤ by ≥.
Need:
0 < d ≤ c / (lg 3 − 2/3)
Therefore, T(n) = Ω(n lg n)
Θ: T(n) = O(n lg n) and T(n) = Ω(n lg n), conclude that T(n) = Θ(n lg n)
Finding the closed form for a sequence
Suppose we have an algorithm to compute all permutations of n things. The order is listed in the tree by position:
<a, b, c, d> as a1, b2, c3, d4
<b, c, a, d> as a3, b1, c2, d3
<d, c, b, a> as a4, b3, c2, d1
The algorithm generates the following recursion tree:
Question: What is the complexity of the algorithm?
Obviously the bottom cost is n! since we are generating all permutations so Ω(n!).
The other n1 levels are:
n+n(n1)+n(n1)(n2)+...+n(n1)(n2)*...*3*2
The actual number of calls for n=4 is: 64
4 + 4(41) + 4(41)(42) + 4(41)(42)(43) =
4 + 4(3) + 4(3)(2) + 4! =
4 + 12 + 24 + 24 = 64
The actual number of calls for n=5 is: 325
5 + 5(51) + 5(51)(52) + 5(51)(52)(53) + 5! =
5 + 5(4) + 5(4)(3) + 5(4)(3)(2) + 5! =
5 + 20 + 60 + 120 + 120 = 325
Determining a tight upperbound requires finding a closed form representation of the summation of the recursion tree calls defined by:
There is an online encyclopedia of integer sequences, that can be searched by providing it with a few terms of a sequence. For example, we can search 1, 4, 15, 64, 325 (terms 1 through 5 of the sequence).
According to the site, the sequence is the number of permutations of nonempty subsets of {1,2,3,...,n}.
If we define the sequence a(n) to be the expression given, we find that it obeys the recursion:a(n) = n + n*a(n1).
It also has the closed formula a(n) = [e*n! – 1], where the symbol [x] is the nearest integer to x, and e is the usual constant 2.718...
The upperbound is then: O(e*n!) = O(n!)
See http://www.research.att.com/~njas/sequences/index.html for the site's main page.