0
$\begingroup$

Show that $2^{\sqrt{n}}$ is not $O(n^{10})$ from the definition of $O()$.


I'm not sure on how to start this problem. From the definition, if we want to prove such an statement, then $\forall c>0, \forall N, \exists n \geq N$ so that $2^{\sqrt{n}} > cn^{10}$. I tried to prove this using L'Hopital's rule for the quotient $\displaystyle \frac{2^{\sqrt{n}}}{n^{10}}$, and showing it goes to $\infty$ as $n$ goes to $\infty$, which is true and would imply that it is not $O(n^{10})$. However, how can we prove such an statement just going from the definition of $O()$? I've tried to square both sides and see what happens, but I don't get any meaningful results.

Thank you for all your help.

$\endgroup$
  • 1
    $\begingroup$ $\frac{2^{\sqrt{n}}}{n^{10}}$ goes to infinity as $n$ increases $\endgroup$ – Exodd Oct 3 '14 at 23:54
1
$\begingroup$

As you pointed out, the easiest way to handle these problems is by using simple calculus. The obvious approach is to look at the limit, as you have suggested (I believe you meant the limit goes to $\infty$ as $n$ goes to $\infty$).

Here's an attempt without calculus. Suppose $2^{\sqrt{x}}\in O\left(x^{10}\right)$. Then there exists $c>0$ and $y$ s.t. for all $x\geq y$, \begin{align*} 2^{\sqrt{x}} & \leq cx^{10}\\ \sqrt{x} & \leq\lg\left(cx^{10}\right)\\ & =\lg c+10\lg x\\ & =C+10\lg x \end{align*} where $C=\lg c$. Then, $$ x\leq\left(C+10\lg x\right)^{2} $$ for all $x\geq y$. If you believe $x\notin O\left(\lg^{2}x\right)$, you arrive at a contradiction.

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