Which of these functions has the fastest asymptotic growth: $n^{1/3}\log_2(n)$ or $\frac{1}{4}(\log_2(n))^4$?

Question

I can't seem to figure out which of the following functions has the fastest asymptotic growth: $n^{1/3}\log_2(n)$ or $\frac{1}{4}(\log_2(n))^4$? Can anyone show me with a proof?

Answer 1

$n^a$ where $a\gt 0$ is always asmptotically faster in growth than $\log_2^b{(n)}$ where $b\gt 0$. The factor of $\log_2{(n)}$ multiplied in just makes the function even faster in growth. A proof comes from taking the limit of the ratio of the two functions: $$\lim_{n\to\infty} \frac{n^a}{\ln^b{(n)}}$$ Now application of L'Hôpital's rule $b$ times changes the limit to $$\lim_{n\to\infty} \frac{a^bn^a}{b!}=\infty$$ Hence the function $n^a$ grows infinitely faster than $\ln^b{(n)}$ for any $a\in\mathbb{R}$ and $b\in\mathbb{N}$. As $$\log_2{(n)}=\frac{\ln{(n)}}{\ln{(2)}}$$ One can extend this result to solve the above problem.