Respuesta :
Answer:
Follows are the solution to this question:
Explanation:
The scale of the subproblem for a node is [tex]\frac{n}{2^i}[/tex] at depth.
The tree then has lg n + 1 and [tex]4^{lg n} = n^2[/tex]leaves.
Complete costs for all depth I nodes for I = 0. 1 , 2, ......, lg n-1 is:[tex]4^i ( \frac{n}{2^i}+ 2 ) = 2^i n + 2\times 4^i.[/tex]
[tex]T(n)= \sum_{ i = 0}\lg n - 1( 2^i n + 2 . 4^i )+ \Theta (n^2)\\\\[/tex]
[tex]= \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)\\[/tex]
verfify the value:
[tex]\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),\\\\[/tex]
Where there is the last stage for [tex]\to cd - 8c -1 \geq 0[/tex].
