No 'C '

Dark Mode

392 views

0 votes

0

1 vote

use recursion tree method for this type of problem. You'll get the answer easily.

like on first level $n^{2}$

/ \

$(n/4)^{2}$ $(n/2)^{2}$

/ \ / \

$(n/16)^{2}$ $(n/8)^{2}$ $(n/8)^{2}$ $(n/4)^{2}$

.......................................

............................ logn level

T(n) = $n^{2}{(1+\frac{5}{16}+(\frac{5}{16})^{2}............logn\, times)}$

T(n)= $n^{2}$(1) (it is decreasing GP so it will be close to 1.)

T(n) = $\Theta (n^{2})$

like on first level $n^{2}$

/ \

$(n/4)^{2}$ $(n/2)^{2}$

/ \ / \

$(n/16)^{2}$ $(n/8)^{2}$ $(n/8)^{2}$ $(n/4)^{2}$

.......................................

............................ logn level

T(n) = $n^{2}{(1+\frac{5}{16}+(\frac{5}{16})^{2}............logn\, times)}$

T(n)= $n^{2}$(1) (it is decreasing GP so it will be close to 1.)

T(n) = $\Theta (n^{2})$

0

0