Can we solve this
T(n) = 2T( n/2 ) + n lg n recurrence equation master theorem I am coming from a link where he is stating that we can't apply here master theorem because it doesn't satisfied any of the 3ree case condition. On the other hand he has taken a another example
T(n) = 27T(n/3) + Θ(n^3 lg n) and find the closed solution
theta(n^3logn) For solving this he used 2nd case of master theorem
If f(n) = Θ(nlogba (lg n)k ) then T(n) ∈ Θ(nlogba (lg n)k+1) for some k >= 0 Here my confusion arises why not we can apply 2nd case here while it is completely fit in 2nd case.
My thought: a = 2 , b =2; let k =1 then
f(n) = theta(n^log_2 2 logn) for k= 1 so T(n) = theta(nlogn) But he as mentioned on this we can't apply master theorem I m confused why not.
Note: It is due to f(n) bcz in
T(n) = 2T( n/2 ) + n lg n
f(n) = nlog n and in
T(n) = 27T(n/3) + Θ(n^3 lg n) *
f(n) = theta(n^3log n)* Please Correct me if I am wrong here.