Question

Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = 4T(n/2 + 2) + n. Use the substitution method to verify your answer.

Answer 1

Answer:

Follows are the solution to this question:

Explanation:

The scale of the subproblem for a node is $\frac{n}{2^i}$  at depth.  

The tree then has lg n + 1 and $4^{lg n} = n^2$leaves.  

Complete costs for all depth I nodes for I = 0. 1 , 2, ......, lg n-1 is:$4^i ( \frac{n}{2^i}+ 2 ) = 2^i n + 2\times 4^i.$

$T(n)= \sum_{ i = 0}\lg n - 1( 2^i n + 2 . 4^i )+ \Theta (n^2)$

        $= \sum_ {i = 0} \lg n - 1 2^i n + \sum_{i = 0} \lg n - 12 \times 4^i + \Theta (n^2)\\\\= [ \frac{ 2\lg n - 1}{ 2 - 1} ]n + 2 \times [ \frac{ 4\lg n - 1}{ 4 - 1} ]n + \Theta (n^2)\\\\= ( 2\lg n - 1) n] + (\frac{2}{3})( 4\lg n - 1)+ \Theta (n^2)\\\\= (n-1)n - \frac{2}{3} (n^2 -1) +\Theta (n^2)\\\\= \Theta (n2)$

verfify the value:

$\to T(n) \leq c (n^2 - dn) \\\\T(n) = T(n) = 4T((\frac{n}{2}) + 2) + n \\\\ \leq 4c [ ((\frac{n}{2}) + 2)2 - d((\frac{n}{2}) + 2) ]+ n \\\\ \leq 4c [ (\frac{n^2}{4} + 2n + 4) - \frac{dn}{2} - 2d)]+ n \\\\\leq cn2 + 8cn + 16c - 2cdn - 8cd + n\\\\\leq cn2 -cdn + 8cn + 16c - cdn - 8cd + n\\\\\leq c(n2 -dn) - (cd- 8c - 1)n - (d - 2). 8c\\\\\leq c(n2 -dn),$

Where there is the last stage for  $\to cd - 8c -1 \geq 0$.