# Recursion Tree Solution

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)