Growth rate of $n^2$ vs $(\log_3(n))^3$

Question

Which grows faster, $n^2$ or $(\log_3(n))^3$? How do I figure out which grows faster in general in these kinds of situations?

Answer 1

Any log loses to any polynomial. You can think it this way: let $p,q$ be any two polynomials, with positive leading coefficients. Then $$ \lim_{x\to\infty}\frac{p(x)}{q(\log x)}=\infty. $$ This can be easily proven using L'Hopital; if $d$ is the degree of $p$, after $d$ applications of L'Hopital the numerator will be a positive constant, while the denominator will go to zero as the derivation process will make all terms of the form $(\log x)^k/x$.

Note that the base $3$ is the log plays no role, as $\log_3x=\log x/\log 3$.