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?
Best Answer
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.