how to solve this recurrence relation

Question

T(n) = 2*T(n/2) + n*logn
 please explain

Comments

use master theorem here.

---

how master can be applied here

---

learn the bigger version of master theorem . that will help.

Answer 1

For T(n)= aT(n/b)+n^k log^p n 

for a>=1, b>1, k>=0,p real no.

compare a and b^k,

                                    1. if a>b^k then T(n)=n^(log a/log b)

                                    2. if a=b^k then 

                                                     .if p>-1, T(n)=n^(log a/log b) log^(p+1) n

                                                     .if p=-1, T(n)=n^(log a/log b)  log log n

                                                     .if p<-1, T(n)=n^(log a/log b)

                                    3. if a<b^k then

                                                      .if p>=0, T(n)=n^k log^p n

                                                      .if p<0, T(n)=n^k

compare a and b^k i.e a=2, b^k=2^1 which implies a=b^k

Since, p >=(-1), so, T(n)=n log^2 n