Recursion Tree
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
                                                                                              
  2. From the tree determine:
    1. # of levels in the tree                 
    2. cost per level                             
    3. # of nodes/level                         
    4. # of nodes in the last level          
    5. cost of the last level (which is based on the number found in 2d)      
  3. Write down the summation using S notation – this summation sums up the cost of all the levels in the recursion tree

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