Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 0 down vote accepted

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

share|improve this answer
    
Then the inequality can be interpreted as one function's growth rate being smaller than the other; correct? (Thanks for your answer) –  Pi_ Sep 14 '12 at 3:26
    
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
    
Thank you very much, you've saved me a headache! –  Pi_ Sep 14 '12 at 4:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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