# Is $n^2=O(2^{log(n)})$?

We have $\lim_{n\to\infty} \frac{n^2}{2^{log(n)}} = \lim_{n\to\infty} \frac{2n}{2^{log(n)}log(2)(1/n)} = \lim_{n\to\infty} \frac{2n^2}{log(2) 2^{log(n)}}$ using L'Hospital's rule. But this process continues because although the power of $n$ in the numerator reduces as we differentiate, the denominator keeps providing the numerator with $n$ due to the differentiation of the $log(n)$ term.

Suppose we continue this process $\lceil{log(n)}\rceil$ times (does this make sense as $n\to \infty$ ?). Then we have $2^{log(n)}$ in the numerator, which cancels out with the $2^{log(n)}$ in the denominator. Does this mean that the limit tends to infinity? Does this mean in fact that $2^{log(n)}=O(n^2)$?

• Suggestion: Throw L'Hopital away by the window and think about what is really $2^{\log n}$. Hint: Power of $n$. – Did Aug 9 '16 at 12:58
• @Did Yes I see. $n^{log(2)}$. This helps. Thank you! – Picasso Aug 9 '16 at 13:11

L'Hopital is not necessary. We have that $2^{\ln n}=\exp(\ln n\ln 2)=n^{\ln(2)}$. Then as $n\to+\infty$, $$\frac{n^2}{2^{\ln(n)}}=\frac{n^2}{n^{\ln 2}}=n^{2-\ln 2}\to +\infty$$ because $\ln(2)<1<2$. Hence $n^2$ is not $O(2^{\ln(n)})$. On the other hand $2^{\ln(n)}=O(n^2)$.