Prove $2^{\sqrt{\log n}}=o(n)$

Question

To my understanding, I need to show the following equals 0.
I tried using L'hopital's rule, but got the same $\lim$ times a constant.

$$ \lim_{n \to \infty} \frac{2^{\sqrt{\log_e n}}}{n} $$

@TheBro21 If it's not otherwise stated, $\log$ always means $\log_e$. — Patrick Stevens, Mar 19 '17 at 09:02
@PatrickStevens I have seen many cases where $\log$ is base 10. $\ln$ is also used to denote the natural logarithm — John K, Mar 19 '17 at 09:03

Adren · Accepted Answer · 2017-03-19T09:32:19.200

Il will consider the logarithm is base $e$, but it doesn't change anything if you consider another base.

You have to prove that :

$$\lim_{n\to\infty}\frac{2^\sqrt{\ln(n)}}n=0$$

Take its logarithm :

$$\ln\left(\frac{2^\sqrt{\ln(n)}}n\right)=\ln(2)\sqrt{\ln(n)}-\ln(n)=\ln(n)\left(\frac{\ln(2)}{\sqrt{\ln(n)}}-1\right)$$

It is clear that the last expression in parenthesis has limit $-1$, hence :

$$\lim_{n\to\infty}\ln\left(\frac{2^\sqrt{\ln(n)}}n\right)=-\infty$$

and the conclusion follows, by composition of limits.

Jacky Chong · Answer 2 · 2017-03-19T09:22:27.157

1

We will use the fact that \begin{align} \sqrt{\log n} \leq \frac{3}{4}\log n \end{align} when $n$ is sufficiently large. Then it follows \begin{align} e^{\sqrt{\log n}} \leq e^{\frac{3}{2}\log\sqrt{n}} = n^{3/4}. \end{align} Hence the rest follows immediately.

edited Mar 19 '17 at 09:22

answered Mar 19 '17 at 09:14

Jacky Chong

25,739

It's worth writing the end of the argument: you get $2^{\sqrt{\log n}}=O(n^{3/4\log 2})=O(n^{0.52})=o(n)$. – Gabriel Romon Mar 19 '17 at 09:22

score 0 · Answer 3 · answered Mar 19 '17 at 09:12

L'Hôpital: $$\lim_{n \to \infty} \frac{2^{\sqrt{\log n}}}{n} = \frac{\log(2)}{2} \lim_{n \to \infty} \frac{ 2^{\sqrt{\log n}}}{n \sqrt{\log (n)}}$$

Therefore if $\lim_{n \to \infty}\frac{2^{\sqrt{\log n}}}{n} = A$ where $A < \infty$, then $A = \frac{\log(2)}{2} \times 0$, since the limit on the right-hand is $0$ by "limit of a product is the product of the limits".

So the limit you seek is either $0$ or $\infty$. That's as far as I quickly see how to go with L'Hôpital.

Note that the expression is $$2^{\sqrt{\log n} - \log(n)/\log(2)}$$ so the limit you seek is $$\exp \left(\log(2) \lim_{n \to \infty} \left[\sqrt{\log n} - \frac{\log n}{\log 2}\right] \right)$$ Substituting $u=\log n$, we need to find $$L = \lim_{u \to \infty} \left[\sqrt{u} - \frac{u}{\log 2}\right]$$ But differentiation shows that the expression in the brackets is negative for $u > \log(2)^2$ and gets more negative approximately linearly, so $L$ must be $-\infty$ and hence your original limit is $0$. (To be more formal, one can argue that your original limit is either $0$ or $\infty$; it can't be $\infty$ because $L \leq 0$, so it must be $0$.)

Prove $2^{\sqrt{\log n}}=o(n)$

3 Answers3