# How to prove that $n^{\log_{2} (n) } = O (2^n)$ ?

While trying to prove that $$n^{\log_{2} (n) } = O (2^n) ,$$ I figured that $$2^n = e^{ n \ln (2) } ,$$ and that $$n^{ \log_{2} (n) } = n^{ \frac{\ln(n) }{ \ln(2) } } = e^{ \ln (n^{ \frac{ \ln(n) }{ \ln(2) }}) } = e^{\frac{(\ln(n))^2} {\ln(2) }} < e^{ (\ln(n))^2 \cdot \ln(2) },$$ so now I only need to prove that there exists some $c > 0$ such that $$(\ln(n))^2 < c \cdot n$$ for all $n > N$ for some $N \in \mathbb{Z}_{>0}$ .

Could you please help me prove this last statement? This would in turn answer the main question.

## 1 Answer

HINT: What is $$\lim_{x\to\infty}\frac{(\ln x)^2}x\;?$$

• @Max: You’re welcome! Nov 26 '13 at 20:52