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

Follows are the solution to this question:

Step-by-step explanation:

The scale of the subproblem for a node is
`(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 ( (n)/(2^i)+ 2 ) = 2^i n + 2* 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 * 4^i + \Theta (n^2)\\\\= [ ( 2\lg n - 1)/( 2 - 1) ]n + 2 * [ ( 4\lg n - 1)/( 4 - 1) ]n + \Theta (n^2)\\\\= ( 2\lg n - 1) n] + ((2)/(3))( 4\lg n - 1)+ \Theta (n^2)\\\\= (n-1)n - (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(((n)/(2)) + 2) + n \\\\ \leq 4c [ (((n)/(2)) + 2)2 - d(((n)/(2)) + 2) ]+ n \\\\ \leq 4c [ ((n^2)/(4) + 2n + 4) - (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`.