3
$\begingroup$

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 ?

$\endgroup$
1
  • $\begingroup$ You will likely find my answer here helpful. $\endgroup$ Aug 30 '17 at 17:03
2
$\begingroup$

$\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$.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – Ian
    Jan 18 '15 at 23:03
  • $\begingroup$ (Alternately you could say that both quotients are bounded by some polynomial.) $\endgroup$
    – Ian
    Jan 19 '15 at 0:11
  • $\begingroup$ @Ian Thanks a lot, finally it's clear now. $\endgroup$
    – the_dude
    Jan 24 '15 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.