Which of these two functions grow asymptotically faster?

Question

Which of these two functions grow asymptotically faster?

$$2^{\sqrt{\log^{1.9}n}}$$

$$n^{1/5}$$

I think the answer should be $2^{\sqrt{\log^{1.9}n}}$. I made an excel spreadsheet with both these functions and the first one goes higher, quicker. Is this a correct way to think about it?

Answer 1

I take the log to be base 2. If it is base $e$ or base 10, then the first function only grows slower.

$$2^{\sqrt{\log^{1.9}(n)}}=2^{\log^{0.95}(n)}=\left(2^{\log(n)}\right)^{\log^{-0.05}(n)}=n^{\log^{-0.05}(n)}$$

But if $n>2^{5^{20}}$, then $\log n>5^{20}$, then $\log^{0.05} n>5$, then $\log^{-0.05} n<\frac15$.

Thus the $n^{1/5}$ function will grow faster, but you won't reach the crossing point in your spreadsheet.

Answer 2

It depends on how you want to compare their growth.

Do you want to show which function is above the other? Or do you want to show that their ratio is either infinite, zero, or a positive number?

For example $n$ can be said to "grow faster" than $n/2+1$ in the sense that $n>n/2+1$ for $n>2$, but they both "grow linearly". Often, we would say that they grow at the same rate since their ratio converges to a non-zero number:

$$ \lim_{n\rightarrow\infty}\frac{n}{n/2+1}=2. $$

I think the most meaningful way to answer your question is to determine

$$ \lim_{n\rightarrow\infty}\frac{n^{1/5}}{2^{(\log n)^{0.95}}}. $$

We can show that for functions $f(n)$ and $g(n)$ which both diverge to infinity as $n\rightarrow\infty$, that $\lim \frac{\log f}{\log g} =\infty$ implies that $\lim \frac{f}{g} =\infty$ (prove this). So taking the $\log$ of both functions gives:

$$ \lim_{n\rightarrow\infty}\frac{1/5 \log n}{(\log 2){(\log n)^{0.95}}}. $$

This definitely diverges, therefore $n^{1/5}$ grows faster asymptotically.