Recursion Tree Solution

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

1. Draw the tree based on the recurrence
                                                                                             

Levels         Cost

n(n+1)/2

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

 

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 = 2⁰n + 2¹n + 2²n + ... + 2^{lg n-1}n

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

 

Guess: T(n) = O(n²)

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

Prove by substitution: T(n) ≤ dn²

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) ≤ dn² - bn

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

Prove by substitution: T(n) ≤ dn² - 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) ≤ dn² - bn

T(1) = 1 ≤ d*1²-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) ≤ dn² - bn, ∀n ≥ n₀ when d=2, b=1 and n₀ = 1,

     T(n) ∈ O(n²)