Recursion Tree Solution

Document last modified: 

Use a recursion tree to determine a good asymptotic upper bound guess on the following recurrence:

where T(n) = 1            when n = 1
T(n-1) + n   when n > 1

Steps:
  1. Draw the tree based on the recurrence
                                                                                              
        Levels         Cost
                     n(n+1)/2
  1. From the tree determine:
    1. # of levels in the tree                  n
    2. cost per level                              n, n-1, n-2, ..., 2, 1
    3. # of nodes/level                          1
    4. # of nodes in the last level           1
    5. cost of the last level (which is based on the number found in 2d)       1
  2. Write down the summation using S notation this summation sums up the cost of all the levels in the recursion tree - see above

    n + n-1 + n-2 + ... + 2 + 1 =

    From Appendix A, p. 1059, arithmetic series.


Use a recursion tree to determine a good asymptotic upper bound on the following recurrence:

where T(n) = 1                  when n = 1
4T(n/2) + n  when n > 1

 

Bottom level has n=1 size problems or T(1)

     Two ways to determine cost:

Computing for each level:

2lg n = nlg 2 = n

2lg nn = n2 = O(n2)

Number of nodes * T(1):

4lg n*T(1) = nlg 4*T(1) = n2*T(1) = O(n2)

 

 

Other lg n -1 levels = 20n + 21n + 22n + ... + 2lg n-1n

Total cost (Appendix A, p. 1060, geometric series)

 

Guess: T(n) = O(n2)

IH:       T(n/2) ≤ d(n/2)2

Prove by substitution: T(n) ≤ dn2

T(n) = 4T(n/2) + n    Recurrence
  ≤ 4[ d (n/2)2] + n    Substitute IH
  = 4[ d (n2/4)] + n  
  = dn2 + n  
  ≤ dn2    
  dn2 + n ≤ dn2     Fails
            n ≤ 0     Require n>0

 

Use substitution subtlety: T(n) ≤ dn2 - bn

IH:       T(n/2) ≤ d(n/2)2 - bn/2

Prove by substitution: T(n) ≤ dn2 - bn

T(n) = 4T(n/2) + n
  ≤ 4[ d (n/2)2 -bn/2]+ n
  = 4[ d (n2/4) - bn/2] + n
  = dn2 - 2bn + n
  ≤ dn2 - bn
Find: b

dn2 -2bn+ n ≤ dn2 - bn

       -2bn+ n ≤ - bn

                 n ≤ bn

                 1 ≤ b

                 b ≥ 1

Find: d > 0

T(n) ≤ dn2 - bn

T(1) = 1 ≤ d*12-b*1

           1 ≤ d-b

      d ≥ b+1

for b=1, d=2 satisfies base case T(1).

T(n) = 1                  when n = 1
4T(n/2) + n  when n > 1

Since T(n) ≤ dn2 - bn, ∀n ≥ n0 when d=2, b=1 and n0 = 1,

     T(n) ∈ O(n2)