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

47 Views Asked by At

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

There are 1 best solutions below

1
On

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