0
$\begingroup$

This question already has an answer here:

Prove, using only the definition of $O()$, that $2^{\sqrt{x}}$ is not $O(x^{10})$.

I have been doing a few exercises on Big O and this is the first time I have encountered the variable in the exponent. I was wondering how to disprove this function. Any help would be appreciated

$\endgroup$

marked as duplicate by Raphael Oct 4 '14 at 8:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – FrankW Oct 3 '14 at 15:49
  • $\begingroup$ For every $c$, find $x_0$ so that $2^{\sqrt{x}} > cx^{10}$ for all $x \geq x_0$. $\endgroup$ – Raphael Oct 4 '14 at 8:39
2
$\begingroup$

Hint: Try converting both functions to the form $e^{f'(x)}$.

$\endgroup$
  • $\begingroup$ Or, since $\log_2$ is an increasing function, take $\log_2$ of both sides and compare the results. $\endgroup$ – Rick Decker Oct 3 '14 at 18:04
  • $\begingroup$ @RickDecker Merely comparing the results isn't enough: $x^2 \notin O(x)$, but $\log(x^2) \in O(\log(x))$. You can take the logs on both sides (and that's what FrankW is suggesting with different wording), but you still need to plug that into the definition of $O$. $\endgroup$ – Gilles Oct 3 '14 at 18:58
  • $\begingroup$ @Gilles. Of course. My point was that it's then clearer that one can't find a $c$ for which $\sqrt{x} \le c\cdot10\cdot\log_2x$. $\endgroup$ – Rick Decker Oct 4 '14 at 17:35
0
$\begingroup$

$O(x^{10})$ is $O(x^k)$ for some constant $k$ (polynomial complexity) whereas $O(2^{\sqrt{x}})=O(2^{x^k})$ is subexponential by definition.

Using De l'Hôpital's rule, you can find the following:

$ \lim_{x\rightarrow\infty} \displaystyle\frac{x^{10}}{2^{\sqrt{x}}} = \lim_{x\rightarrow\infty} \frac{\frac{\delta x^{10}}{\delta x}}{\frac{\delta 2^{\sqrt{x}}}{\delta x}}=0 $

which shows that the denominator grows faster than the numerator. You can actually differentiate the fraction until you get a constant numerator while the denominator will always stay a function of $x$.

$\endgroup$

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