0

Suppose that $f(x)$ is $O(g(x))$. Does it follow that enter image description here ?

First, I start from enter image description here for some $c$ is a real number. Then, I find enter image description here. But, if i start from enter image description here, I just find enter image description here. I confused with that different form.

ASB
  • 3,999
james brown
  • 460
  • $3^x \neq O(2^x)$ (prove by definition) , so it is not hard to find $f(x)=O(x)$ but $2^{f(x)} \neq O(2^x)$ – UserB95 Mar 10 '15 at 11:20

1 Answers1

1

Consider $f(x) = x$ and $g(x) = x/2$ for $x\geq 0$. Then, $f(x) = 2g(x) = O(g(x))$, but you don't have $2^x = O(2^{x/2})$ (if $2^x \leq c 2^{x/2}$, then $x \leq \log(c) +x/2$, which is absurd). The answer to your question is no.

Goulifet
  • 822