master theorem f(n) = nlogn

Question

I am working Problem 4-3 from Introduction to Algorithm, 3rd Edition. And I am asked to find the asymptotic upper and lower bounds for T(n):

T(n) = 4T(n/3) + n lg(n)

I have browsed online for the solution and the solution says:

By master's theorem, we get T(n) ∈ Θ(n^log₃(4))

I believe that the solution assumes that n^log₃4 is asymptotically larger than n lg(n)? But why is this true? I will be grateful if someone can help me understand!

Answer 1

In layman's terms:

We need to compare grow of n*log(n) with n^1.25 (log3(4)~1.26)

Divide both functions by n

  log(n) vs n^(1/4)

Both are increasing.
Derivatives of both functions

  n^(-1)  vs n^(-3/4)  

Derivative of the second one is clearly larger, so the second function grows faster

We can see that plots of these functions intersect and power function becomes larger for big n values - for any power>1