master theorem

Question

T(n)=4T(n/2)+n/logn

this can be solved by master theorem but why

t(n)=2t(n/2)+n/logn can't be solved by master theorem ?

Comments

Caption

 

Answer 1

T(n)=4T(n/2)+n/logn 

here n^log₂4  = n²  > n/logn  ( i.e. not log n time big).

 

T(n)=2T(n/2)+n/logn

here  n^log₂2  = n > n/logn  ( i.e.  log n time big). which is not the case of master thoerm but done by extented master theorm.

Comments

but a/c to extended master theoram

 

so answer is coming as O(n2) ..ryt?

---

@cse23. Yes, but precisely theta(n^2).

---

for $T(n)=4T(n/2)+n/logn$

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

and for $T(n)=2T(n/2)+n/logn$

     $T(n)=\theta(loglogn)=\theta(log^{2}n)$

---

it should be theta(n*loglogn) for 2T(n/2) +n/logn