edited by
604 views
0 votes
0 votes

…………………………..

edited by

1 Answer

1 votes
1 votes
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})$

Related questions

0 votes
0 votes
1 answer
1
2 votes
2 votes
1 answer
2
0 votes
0 votes
1 answer
3
Shubham Aggarwal asked Nov 13, 2018
1,191 views
Which of the following functions given by their recurrences grows the fastest asymptotically?$T(n) = 8T(n/4) + 100n^2$$T(n) = 81T(n/9) + 10n^2$$T(n) = 16T(n/4)+ 100(n \lo...
0 votes
0 votes
1 answer
4