Chapter 4 - Recursion Tree

Document last modified: 

Uses:

Note: the bound sought will be one of the following:

Steps:

  1. Draw the tree based on the recurrence

  2. 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)

  3. Write down the summation using ∑ notation – this summation sums up the cost of all the levels in the recursion tree

  4. Recognize the sum or look for a closed form solution for the summation created in 3).  Use Appendix A.

  5. 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).

  6. 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

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(n-1)
|
1
2 T(n-2)
|
1
: :    
n-1 T(1) 1
  Total n

Height n-1

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

0 ≤ T(n) ≤ cn must hold

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

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 n0 to satisfy O definition

Verify: TR(n) ≤ TC(n)                       Recurrence  ≤  Closed-end

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

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

Try n0 = 1
TR(n) TC(n)    
TR( 1 ) TC( 1 )    
TR( 1-1 ) + 1 TC( 1 )   Substitute
recurrence
1 c(1)   T( 0 ) does
not exist
1 c    
c 1    

 Succeeds for n0 = 1 

Try n0 = 2
TR(n) TC(n)    
TR( 2 ) TC( 2 )    
TR( 2-1 ) + 1 TC( 2 )   Substitute
recurrrence
T( 1 ) + 1 c(2)   T( 1 ) = 1
1 + 1 2c    
c 1    

 Succeeds for n0 = 2 

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

 

Example -Recursion Tree - Finding O

T(1) = 5                 n=1

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

Problem size 4
Level n   Nodes
0 4   20=1
1 3   21=2
2 2   22=4
3 1   23=8
  Total 24-1 = 15

Height 3

Levels 4

                 
                  n=4

a) # levels = n
b) # nodes/level = 2i, i=0 to 3
c) # bottom nodes = 23
d) Cost/level =3*2i, i=0 to n-2
e) Bottom cost = 5*2n-1 = 5*23
f) Cost levels 0, 1, 2

 
                           by A5, page 1147

Problem size 4
Level Nodes   Cost
0 20   3*20=3
1 21   3*21=6
2 22   3*22=12
3 23   5*23=40
  Total 61

n=4  

 


 
T(n) = 3(2n-1-1) + 5*2n-1
3(24-1-1)+5(24-1) = 3(23-1)+5(23)
  = 3*7+5*8
  = 21+40
  = 61

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

T(n) = 3(2n-1-1) + 5*2n-1

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

By definition of Big-O:

T(n) = 2T(n-1) + 3 ≤ c2n must hold

Show:

T(n) = 2T(n-1) + 3 ≤ c2n

Inductive Hypothesis:

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

T(n) = 2T(n-1) + 3             Recurrence
  ≤  2c(2n-1) + 3           Substitute IH
  = c2n + 3
  ≤ c2n                         Fails

Substitution Subtlety

Show:

T(n) = 2T(n-1) + 3 ≤ c2n - b

Inductive Hypothesis:

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

T(n) = 2T(n-1) + 3                     Recurrence
  ≤  2[c(2n-1) - b] + 3           Substitute IH
  = c2n -2b + 3
  ≤ c2n - b                    
Solve c2n -2b + 3 ≤ c2n - b 
                  3 ≤ b

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

T(1) = 5                 n=1

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

Verify: TR(n) ≤ TC(n)                       Recurrence  ≤  Closed-end

     TR(n) = 2TR(n-1) + 3           Recurrence

     TC(n) = c2n - b                     Closed-end bounds solution for O(2n)

Try n0 = 2
TR(n) TC(n)    
TR( 2 ) TC( 2 )    
2TR( 2-1 ) + 3 TC( 2 )   Substitute
2T( 1 ) + 3 c22 - b   T( 1 ) = 5
10 + 3 4c - 3   Let b = 3
13 4c -3    
16 4c    
c 4    

 Succeeds for n0 = 2 

O(n): T(n) ≤ c2n - b ≤ c2n for c ≥ 4, ∀n ≥ n0 = 2

 

Question 4.12.1

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

Draw 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)  
       return            
T(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      40=1     5 = 40*5


1      41=4
     20 = 41*5


2      42=16
   90 = 42*5


3      43=64
   384 = 43*6    lg 8 = 3

Cost for Level 0 through lg n-1:   

for n = 8:    5 * (82-1)/3 = 5 * 21 = 105

Cost for Level lg n:                        6 * 4lg n = 6 * nlg 4 = 6 * n2

for n = 8:    6 * 4lg 8 = 6 * 64 = 384

Total cost:

                                 for n = 8:    105 + 384 = 489

O(n2) Guess:             5 * (n2-1)/3 + 6 * n2

 

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;
       return
T(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      40=1     8 = 40*n/20 = (4/2)0*n


1      41=4
     16 = 41*n/21 = (4/2)1*n


2      42=16
   32 = 42*n/22 = (4/2)2*n


3      43=64
   384 = 43*6

Cost for Level 0 through lg n-1:   

for n = 8:    (82-8) = 56

Cost for Level lg n:                        6 * 4lg n = 6 * nlg 4 = 6 * n2

for n = 8:    6 * 4lg 8 = 6 * 64 = 384

Total cost:

                                 for n = 8:    56 + 384 = 440

O(n2) Guess:             (n2-n) + 6 * n2 = 7n2 - 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 n2
       f(n/3)                
       f(n/3)
       for(i=1; i<=n; i++)
             for(j=1; j<=n; j++) print i*j;
       return

T(n) = 2T(n/3) + n2     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        20=1     20*(n/30)2 = (2/32)0*n2
1        21=2     21*(n/31)2 = (2/32)1*n2

2        22=4
     22*(n/32)2 = (2/32)2*n2

3        23=8     23*(n/33)2 = (2/32)3*n2

   :         :              :
log3n  2
log3n    T(1)*2log3n = T(1)*nlog32



Cost for Level 0 through log3 n-1:

Cost for bottom, Level log3 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 > 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.

  1. 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 = 2lg n for height lg n dividing problem by 2 each time.

Recall: alogan = n

so 2log2n = 2lg n =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
  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

  2. Write down the summation using ∑ notation. Summation of cost for lg n levels in the recursion tree + bottom level.

  3. 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.

  4. 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)
  5. 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 ≥ n0

    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 20 = 0     at odds with d  > 0, d ≥ c

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

    Use as basis:

    T(2) ≤ d2 lg 21 = 2d

    By the recurrence, where c is 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

  6. O(n lg n): 0 ≤ T(n) ≤ dn lg n for d > 0, for all n ≥ n0

    satisfied by d ≥ 2c > 0, for all n ≥ n0 = 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) = |
           | 3
T(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: log3n

Levels: log3n + 1

Cost per level: bn

Bottom (size n=1 problem):

Cost per node: b

Nodes: 3log3n = n

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

log3n - the number of recurrences (levels preceding bottom)

O(n log3n): 0 ≤ T(n) ≤ cn log3n

Recurrence:

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

Guess: T(n) = bn log3n + bn = O(n log3n)

Basis:

T(1) = 3T(1/3) +  b*1 = b ≤ cn log3n = c1 log3 1 = 0     at odds with T(1) = b and b > 0

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

Choose n0=3

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

T(3) ≤ c3 log33 = 3c

Prove basis holds for n0

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 log33 = 3c

6b ≤ 3c

2b ≤ c

so let c = 2b

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

T(n/3) ≤ c(n/3) log3(n/3) is true

Show: T(n) ≤ cn log3n

T(n) = 3T(n/3) + bn                                                 Recurrence
  ≤ 3[c(n/3) log3(n/3)] + bn                           IH substitution
  = 3[c(n/3) log3n - c(n/3) log33] + bn                Recall that log a/b = log a - log b
  = 3[c(n/3) log3n - c(n/3)] + bn                         log33=1
  = 3c(n/3) log3n - 3c(n/3) + bn
  = cn log3n - cn + bn
  ≤ cn log3

cn log3n - cn + bn ≤ cn log3n        

              -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 log3n) for c = 2b and n0=3

 

Question 4.13 - For:

           | c                             if n = 1
T(n) = |
           |
4T(⌊n/2⌋) + cn     if n > 1
  1. From the tree determine:
    1. # of levels in the tree of height lg n:

       

    2. cost per level:

       

    3. # of nodes in the last level, problem size n=1:

       

    4. cost of the last level (which is based on the number found in 2c times base cost):

       

  2. Write down the summation using ∑ notation. Summation of cost for lg n levels in the recursion tree + bottom level.

     

  3. Find closed form solution for the summation created in 3) often using Appendix A.

     

  4. 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( ? )
  5. 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):

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.