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?


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$.

  • $\begingroup$ Then the inequality can be interpreted as one function's growth rate being smaller than the other; correct? (Thanks for your answer) $\endgroup$
    – Pi_
    Sep 14 '12 at 3:26
  • $\begingroup$ A lot smaller. The growth rate of $2n$ is smaller than that of $3n$, but their quotient doesn't go to zero. $\endgroup$ Sep 14 '12 at 3:44
  • $\begingroup$ Thank you very much, you've saved me a headache! $\endgroup$
    – Pi_
    Sep 14 '12 at 4:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.