Question about time complexity and Master Theorem

Question

I'm quite new to algorithm and I encountered a question that I don't know how to apply Master Theorem:

We have an algorithm A, which solves P by creating 3 subproblems, each of size 2n/3, recursively solving each subproblem, and then combining solutions in O(nlogn) time. Would this algorithm have a better running time than O(n)? Prove your answer.

What I know here is a=3, b=3/2, but how can I deal with O(nlogn)?

Answer 1

Henve, the recursive formula is T(n) = 3T(2n/3) + O(n\log(n)). As f(n) = O(n\log(n)) = O(n^{\log(3)/\log(1.5)}) ~ O(n^{2.7}), from the master theorem we can say T(n) = \Theta(n^{2.7}). Therefore, T(n) = \Omega(n^{2.7}).