# Master Theorem. How is $n\log n$ polynomially larger than $n^{\log_4 3}$

I was reading Master theorem from CLRS, and it said that $n\log n$ is polynomially larger than $n^{\log_4 3}$ while

$n\log n$ is not polynomially larger than $n$.

What does it mean to be polynomially larger, and how can I develop intuition for it ?

• You will likely find my answer here helpful. Aug 30 '17 at 17:03

$\log_4(3)<1$ , so $n^{log_4(3)}<n<n\ log(n)$

"Polynomially larger" means that the quotient of the two functions does not exceed some polynomial function, here $n^2$.

• I think that's a bit misleading. More accurately, the quotient is asymptotically larger than one (nonconstant) polynomial and asymptotically smaller than another (nonconstant) polynomial (where "polynomial" in this context permits fractional exponents). Here for instance the quotient is asymptotically smaller than $n^{0.3}$ but asymptotically larger than $n^{0.2}$, since $1-\log_4(3) \approx 0.207$.
– Ian
Jan 18 '15 at 23:03
• (Alternately you could say that both quotients are bounded by some polynomial.)
– Ian
Jan 19 '15 at 0:11
• @Ian Thanks a lot, finally it's clear now. Jan 24 '15 at 20:33