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

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

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

• 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. – FrankW Oct 3 '14 at 15:49
• For every $c$, find $x_0$ so that $2^{\sqrt{x}} > cx^{10}$ for all $x \geq x_0$. – Raphael Oct 4 '14 at 8:39

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

• Or, since $\log_2$ is an increasing function, take $\log_2$ of both sides and compare the results. – Rick Decker Oct 3 '14 at 18:04
• @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$. – Gilles Oct 3 '14 at 18:58
• @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$. – Rick Decker Oct 4 '14 at 17:35

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