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 per-level costs.
- Sum all the per-level 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 Big-O

“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:
1. # of levels in the tree
2. cost per level
3. # of nodes in the last level
4. 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 Big-O, 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 (n-1) * n;
}

n! is defined by the recurrence:

F(1) = 1              for n=1
F(n) = F(n-1)*n   for n>1

The run time cost, T(n), is defined by the recurrence:

T(1) = 1                   for n=1
T(n) = T(n-1) + 1     for all n>1

where 1 is the running time for each execution of the factorial function.

Backward Substitution method for exact closed-end equation - T(n) = n

T(n) = T(n-1) + 1 = [ T(n-2)+1 ] + 1 Substitute T(n-2)+1 for T(n-1)

= T(n-2) + 2 = [ T(n-3)+1 ] + 2 Substitute T(n-3)+1 for T(n-2)

= T(n-3) + 3 = [ T(n-4)+1 ] + 3 Substitute T(n-4)+1 for T(n-3)

= T(n-4) + 4

After i substitutions:

T(n) = T(n-i) + T(n-i+1) + ... + 1 + 1

Initial condition: T(1) = T(n-i)

n-i=1 or i = n-1

T(1) = T(n-i) + i

       = T(1) + n-1

       = 1 + 0 = 1

Closed-end formula:

T(n) = T(1) + n-1 = 1 + n-1 = n

Prove by induction:

T(n) = T(n-1)+1 = n

Base:    T(1) = 1                                          by recurrence definition
             T(2) = T(2-1) + 1 = T(1) + 1 = 2

IH:        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(n-1) + 1     for all n>1

Recursion Tree

Level n Cost

0 4 → 1

1 3 → 1

2 2 → 1

3 1 → 1

Total 4

Height 3

Levels 4

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 Big-O:

0 ≤ T(n) ≤ cn must hold

For O(n) must prove: 0 ≤ T(n) ≤ cn for c > 0, for all n ≥ n₀

Inductive Hypothesis:

T(k-1) ≤ c(k-1)

Show:

T(k) = T(k-1) + 1 ≤ ck

T(k) = T(k-1) + 1            Recurrence

≤ c(k-1) + 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₀ to satisfy O definition

Verify: T_R(n) ≤ T_C(n)                       Recurrence ≤ Closed-end

     T_R(n) = T_R(n-1) + 1             Recurrence

     T_C(n) = cn                           Closed-end bounds solution for O(n)

Try n₀ = 1

T_R(n)	≤	T_C(n)
T_R( 1 )	≤	T_C( 1 )
T_R( 1-1 ) + 1	≤	T_C( 1 )	Substitute recurrence
1	≤	c(1)	T( 0 ) does not exist
1	≤	c
c	≥	1

Succeeds for n₀ = 1

Try n₀ = 2

T_R(n)	≤	T_C(n)
T_R( 2 )	≤	T_C( 2 )
T_R( 2-1 ) + 1	≤	T_C( 2 )	Substitute recurrrence
T( 1 ) + 1	≤	c(2)	T( 1 ) = 1
1 + 1	≤	2c
c	≥	1

Succeeds for n₀ = 2

O(n): 0 ≤ T(n) ≤ cn for c ≥ 1, for all n ≥ n₀= 1 or 2

Example -Recursion Tree - Finding O

T(1) = 1 n=1

T(n) = 2T(n-1) + 1 n>1

Recursion Tree

Level	n	Cost
0	4	2⁰=1
1	3	2¹=2
2	2	2²=4
3	1	2³=8
	Total	2⁴-1 = 15

Height 3

Levels 4

n=4

a) # levels = n
b) # nodes/level = 2ⁱ, i=0 to n-1
c) # bottom nodes = 2^n-1
d) Cost/level =2ⁱ, i=0 to n-1
e) Bottom cost = 2^n-1
f)
by A5, page 1147

Level	Nodes	Cost
0	2⁰	2⁰=1
1	2¹	2¹=2
2	2²	2²=4

n-1	2^n-1	2^n-1
	Total	2ⁿ-1

Cost

Recursion tree provides guess: T(n) = O(2ⁿ)

Show: T(n) = O(2ⁿ)

By definition of Big-O:

T(n) = 2T(n-1) + 1 ≤ c2ⁿ must hold

Show:

T(n) = 2T(n-1) + 1 ≤ c2ⁿ

Inductive Hypothesis:

T(n-1) ≤ c(2^n-1)

T(n) = 2T(n-1) + 1             Recurrence

≤ 2c(2^n-1) + 1           Substitute IH

= c2ⁿ + 1

≤ c2ⁿ                         Fails

Substitution Subtlety

Show:

T(n) = 2T(n-1) + 1 ≤ c2ⁿ - b

Inductive Hypothesis:

T(n-1) ≤ c(2^n-1) - b

T(n) = 2T(n-1) + 1                     Recurrence

≤ 2[c(2^n-1) - b] + 1           Substitute IH

= c2ⁿ -2b + 1

≤ c2ⁿ - b

Solve c2ⁿ -2b + 1 ≤ c2ⁿ - b

                1 ≤ b

Base or boundary conditions: Now find c and n₀ to satisfy O definition

Verify: T_R(n) ≤ T_C(n)                       Recurrence ≤ Closed-end

     T_R(n) = 2T_R(n-1) + 1           Recurrence

     T_C(n) = c2ⁿ - b                     Closed-end bounds solution for O(2ⁿ)

Try n₀ = 2

T_R(n) ≤ T_C(n)

T_R( 2 ) ≤ T_C( 2 )

2T_R( 2-1 ) + 1 ≤ T_C( 2 ) Substitute

2T( 1 ) + 1 ≤ c2² - b T( 1 ) = 1

2 + 1 ≤ 4c - b Let b = 1

4 ≤ 4c

c ≥ 1

Succeeds for n₀ = 2

O(n): T(n) ≤ c2ⁿ - b ≤ c2ⁿ for c ≥ 1, for all n ≥ n₀= 2

Question 4.12.1

| 2 if n = 1
T(n) = |
| 3T(n-1) + 2 if n > 1

Draw the recursion tree.

Determine the number of nodes and cost at each level.

Determine the total cost for all levels (i.e. in summation form).

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 > 1

Use 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

2T(n/2) + cn

For each of size n/2 subproblems, cost:

cn/2 + 2T(n/4)

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.

Recall: _a^logaⁿ = n

so ₂^log2ⁿ = ₂^lg ⁿ =n

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 > 1

Can ignore ⌊ ⌋ by simplifying assumption that n is a power of 2.

Steps using recursion tree continued.

| c if n = 1
T(n) = |
| 2T(n/2) + cn if n > 1

From the tree determine:
1. # of levels in the tree of height lg n:
  
  lg n + 1
2. cost per level:
  
  cn
3. # of nodes in the last level, problem size n=1:
  
  n
4. cost of the last level (which is based on the number found in 2c times base cost):
  
  T(1) * n = cn
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.

Total: cost of each level * the number of levels + cost of bottom level.
Use closed form solution as “guess” in terms of Big-O, or Θ, or Ω (depending on which type of asymptotic bound is being sought).

T(n) = cn lg n + cn

= cn lg n + O(n)

= O(cn lg n) + O(n)

= O(n lg n)

Then use Substitution Method or Master Method to prove that the bound is correct.

By definition of Big-O, 0 ≤ T(n) ≤ d * n lg n

Substitution Method for O(n lg n): 0 ≤ T(n) ≤ dn lg n

For O(n lg n) must prove: 0 ≤ T(n) ≤ dn lg n for d > 0, for all n ≥ n₀

Assume n is a power of 2 to avoid floor and ceil complications to our guess.

           | c                   if n = 1
T(n) = |
           | 2T(n/2) + cn if n > 1

Inductive Hypothesis:

Assume: T(k/2) ≤ d k/2 lg k/2

Show:     T(k) = 2T(k/2) + ck ≤ d * k lg k

T(k) = 2T(k/2) + ck                       Recurrence

≤ 2( dk/2 lg k/2 ) + ck         Substitute IH

= dk lg k/2 + ck

= dk lg k - dk lg 2 + ck

= dk lg k - dk + ck

≤ dk lg k

Find d that satisfies last two lines.

dk lg k - dk + ck ≤ dk lg k

- dk + ck ≤ 0

ck ≤ dk

c ≤ d

Satisfied by d ≥ c

Basis:

T(1) = 2T(1/2) + c*1 = c ≤ d1 lg 1 = d1 lg 2⁰ = 0     at odds with d > 0, d ≥ c

Since need n ≥ n₀ for n a power of 2, choose n₀= 2

Use as basis:

T(2) ≤ d2 lg 2¹ = 2d

By the recurrence, where cis the constant divide and combine time:

           | c                      if n = 1
T(n) = |
           | 2T(n/2) + cn if n > 1

T(2) = 2T(2/2) + 2c

= T(1) + T(1) + 2c

= c + c + 2c

= 4c

Need T(2) = 4c ≤ d2 lg 2 = 2d

           4c ≤ 2d

so let               d= 2c
Satisfies d = 2c ≥ c

O(n lg n): 0 ≤ T(n) ≤ dn lg n for d > 0, for all n ≥ n₀
satisfied by d ≥ 2c> 0, for all n ≥ n₀= 2

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 > 1

where 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₃n

Levels: log₃n + 1

Cost per level: bn

Bottom (size n=1 problem):

Cost per node: b

Nodes: 3^log₃ⁿ = n

3 - the number of subproblems created each recurrence (level)

log₃n - the number of recurrences (levels preceding bottom)

O(n log₃n): 0 ≤ T(n) ≤ cn log₃n

Recurrence:

           | b                   if n = 1
T(n) = |
           | 3T(n/3) + bn if n > 1

Guess: T(n) = bn log₃n + bn = O(n log₃n)

Basis:

T(1) = 3T(1/3) + b*1 = b ≤ cn log₃n = c1 log₃ 1 = 0     at odds with T(1) = b and b > 0

Need to establish inductive basis for n ≥ n₀ for n₀ of our choosing:

Choose n₀=3

Use as inductive basis (not the recurrence basis which is T(1)=b):

T(3) ≤ c3 log₃3 = 3c

Prove basis holds for n₀

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 = 3c
6b ≤ 3c

2b ≤ c

so let c= 2b

IH: Assume holds for n/3, that is:

T(n/3) ≤ c(n/3) log₃(n/3) is true

Show: T(n) ≤ cn log₃n

T(n) = 3T(n/3) + bn                                                 Recurrence

≤ 3[c(n/3) log₃(n/3)] + bn                           IH substitution

= 3[c(n/3) log₃n - c(n/3) log₃3] + bn                Recall that log a/b = log a - log b

= 3[c(n/3) log₃n - c(n/3)] + bn                         log₃3=1

= 3c(n/3) log₃n - 3c(n/3) + bn

= cn log₃n - cn + bn

≤ cn log₃n
cn log₃n - cn + bn ≤ cn log₃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₃n) for c = 2b and n₀=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 Big-O, 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₃n full levels,
after log_3/2n levels, the problem size is down to 1;

log₃n ≤ log_3/2n

Height log_3/2n

Recall that dividing n = 2ⁱ size problem into 1/2 size problems has a tree height:
lg n = log_2/1n = log_2/1(2/1)ⁱ=log₂2ⁱ = 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)²n → ... → 1

(2/3)^kn=1 when k=log_3/2 n the height is log_3/2 n

Solve for k in (2/3)^kn=1

n = (3/2)^k

log_3/2n=log_3/23/2^k=k

Cost ≤ cn log_3/2n

Expect cost to be at most: # levels * cost at each level = cn log_3/2n 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₂n has 2^log₂ⁿ = n^log₂² = n leaves (at bottom).

The complete binary tree leaves are: 2^log_3/2ⁿ = n^log_3/2²

Upper bound guess: dn log_3/2 n = O(n lg n) for some positive constant d.

Note: log_3/2 n/log₂ n= (log₂ n*log_3/2 2)/ log₂ 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 n-1 levels are:

n+n(n-1)+n(n-1)(n-2)+...+n(n-1)(n-2)*...*3*2

The actual number of calls for n=4 is: 64

4 + 4(4-1) + 4(4-1)(4-2) + 4(4-1)(4-2)(4-3) =

4 + 4(3) + 4(3)(2) + 4! =

4 + 12 + 24 + 24 = 64

The actual number of calls for n=5 is: 325

5 + 5(5-1) + 5(5-1)(5-2) + 5(5-1)(5-2)(5-3) + 5! =

5 + 5(4) + 5(4)(3) + 5(4)(3)(2) + 5! =

5 + 20 + 60 + 120 + 120 = 325

Determining a tight upper-bound requires finding a closed form representation of the summation of the recursion tree calls defined by:

There is an on-line 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).

http://www.research.att.com/~njas/sequences/A007526

According to the site, the sequence is the number of permutations of non-empty 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(n-1).

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 upper-bound is then: O(e*n!) = O(n!)

See http://www.research.att.com/~njas/sequences/index.html for the site's main page.

T(n)	= T(n-1) + 1	= [ T(n-2)+1 ] + 1	Substitute T(n-2)+1 for T(n-1)
	= T(n-2) + 2	= [ T(n-3)+1 ] + 2	Substitute T(n-3)+1 for T(n-2)
	= T(n-3) + 3	= [ T(n-4)+1 ] + 3	Substitute T(n-4)+1 for T(n-3)
	= T(n-4) + 4

T(k+1)	= T((k+1)-1) + 1 Recurrence definition
	= T(k) + 1
	= k + 1 IH: T(k) = k

T(k)	= T(k-1) + 1 Recurrence
	≤ c(k-1) + 1 Substitute IH
	= ck - c + 1
	≤ ck
Solve	ck - c + 1 ≤ ck
	-c + 1 ≤ 0
	-c ≤ -1
	c ≥ 1

T(n)	= 2T(n-1) + 1 Recurrence
	≤ 2c(2^n-1) + 1 Substitute IH
	= c2ⁿ + 1
	≤ c2ⁿ Fails

T(n)	= 2T(n-1) + 1 Recurrence
	≤ 2[c(2^n-1) - b] + 1 Substitute IH
	= c2ⁿ -2b + 1
	≤ c2ⁿ - b
Solve	c2ⁿ -2b + 1 ≤ c2ⁿ - b
	1 ≤ b

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)

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 = 3c 6b ≤ 3c 2b ≤ c
so let	c= 2b

T(n)	= 3T(n/3) + bn Recurrence
	≤ 3[c(n/3) log₃(n/3)] + bn IH substitution
	= 3[c(n/3) log₃n - c(n/3) log₃3] + bn Recall that log a/b = log a - log b
	= 3[c(n/3) log₃n - c(n/3)] + bn log₃3=1
	= 3c(n/3) log₃n - 3c(n/3) + bn
	= cn log₃n - cn + bn
	≤ cn log₃n cn log₃n - cn + bn ≤ cn log₃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

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)