1
$\begingroup$

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)$?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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