# Asymptotic growth comparison

When comparing the two functions: $2^{\sqrt{\log_2 n}}$ and $\sqrt{n}$ is it correct to say: \begin{align*} \lim_{n \to \infty} \frac{2^{\sqrt{\log_2 n}}}{\sqrt{n}} & = \lim_{n \to\infty} \frac{\log_2(2^{\sqrt{\log_2 n}})}{\log_2(\sqrt{n})} \\ & = \lim_{n \to \infty} \frac{\sqrt{\log_2 n}}{0.5 \cdot \log_2 n} \\ & = 0 \end{align*} Hence $2^{\sqrt{\log_2 n}} < \sqrt{n}$

If it isn't, why isn't it?

Thanks!

EDIT: What I mean here is, I know the limits are not equivalent but taking the limit of the ratio of the log of the two functions tells us which one is bigger when n is large (i.e. it doesn't bound either function's asymptotic growth) allowing us to simply classify one function as being smaller than the other in terms of growth rate. That is because the logarithm is a positive increasing function on the range we care about. My question might not have been clear enough... I meant to ask if this approach yielded mathematically correct result and only that.

-

I'd rather write $$2^{\sqrt{\log_2n}}/\sqrt n=2^{\sqrt{\log_2n}-(1/2)\log_2n}$$ and then note $$\sqrt{\log_2n}-(1/2)\log_2n\to-\infty$$ as $n\to\infty$ so the limit is, indeed, zero. This doesn't prove $2^{\sqrt{\log_2n}}\lt\sqrt n$ for all $n$, but certainly implies that inequality for all sufficiently large $n$.
A lot smaller. The growth rate of $2n$ is smaller than that of $3n$, but their quotient doesn't go to zero. –  Gerry Myerson Sep 14 '12 at 3:44