392 views

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

No   'C '
Cant we do approximation as below

T(n)=T(n/2) + T(n/2) + $n^2$

==> T(n)= 2T(n/2) + $n^2$

By masters theorem : its $\theta(n^2)$
T(n)>=2*T(n/4)+n^2

=> T(n)>=θ($n^2$)  =>T(n)= Ω($n^2$)

T(n)<=2*T(n/2)+n^2
=>T(n)<=θ($n^2$) => T(n)= O($n^2$)

we can conclude from both T(n)=θ($n^2$)

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

Ooh..

T(n)>=2*T(n/4)+n^2

And

T(n)<=2*T(n/2)+n^2

Both the lower and upper bound will give Theta(n^2) right?

I was doing some mistake before..
yes this way it will give $\theta(n^{2})$ but in my approach i have shown only the upper bound of this means $O(n^{2})$.
It is type recurrence relation

R u sure last variable always gives complexity?

1
295 views