1

Is $x2^x = O(2^x)$? Intuitively it seems like the answer is no. But if we write $x2^x=2^{\log x + x}$ then the answer (to me) is unclear. Thanks in advance!

lollab
  • 73

2 Answers2

4

Answer is no. Assume that

$$x2^x=O(2^x)$$

Then there exists $M>0$ and $X>0$ such that $x\geq X$ implies

$$x2^x\leq M2^x$$

But then for $x=\max\{2M,X\}$ we have that

$$x2^x\geq 2M 2^x>M2^x$$

which is a contradiction since $x\geq X$. We conclude $x2^x\neq O(2^x)$.

QC_QAOA
  • 11,796
  • It kinda seems like this proof only depends on the fact that $f(x) = 2^x$ is a positive-real-valued map defined on the real line (i.e. that maybe $xf(x)\neq O(f(x))$ for any such f or something like this). – Countable Feb 23 '21 at 05:24
  • @Countable Yes, thats very true – QC_QAOA Feb 23 '21 at 05:29
0

Use the definition of $O(.)$ with limits:

$\lim\limits_{x→∞} \frac{f(x)}{g(x)} \ne ∞ \implies f = O(g)$

Let $f(x) = x2^x$, $g(x)=2^x$

Then $\lim\limits_{x→∞} \frac{f(x)}{g(x)} = \lim\limits_{x→∞} \frac{x2^x}{2^x} = \lim\limits_{x→∞}x = ∞$ then we can't say $x2^x=O(2^x)$

To the contrary, if we let $f(x) = 2^x$, $g(x)=x2^x$,

$\lim\limits_{x→∞} \frac{f(x)}{g(x)} = \lim\limits_{x→∞} \frac{2^x}{x2^x} = \lim\limits_{x→∞}\frac{1}{x} = 0 \implies 2^x=o(x2^x)$

Sandipan Dey
  • 2,111