in Algorithms edited by
392 views
0 votes
0 votes

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

in Algorithms edited by
by
392 views

4 Comments

No   'C '
0
0
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)$
0
0
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$)
0
0

1 Answer

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

4 Comments

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..
0
0
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})$.
0
0
It is type recurrence relation

R u sure last variable always gives complexity?
0
0