0
$\begingroup$

Prove $$ f(x) = 2^x + x^2 $$ It is of the order $2^x$ or $f(x)$ is of the order O($2^x$). So far I've got,

$$|f(x)| = 2^x + x^2 \le |2^x| + |x^2| = 2^x + x^2 \le 2^x + 2^x$$

I have no idea how to get this to become just $2^x$ or if I am even doing this right. Any guidance is appreciated.

$\endgroup$
6
  • 1
    $\begingroup$ Do you know whether $2 f(x)$ is $O(f(x))$? What does the big "$O$" mean? $\endgroup$ Oct 22, 2019 at 15:37
  • $\begingroup$ You don't have to make it into $2^x$. Note that the definition of $O(2^x)$ gives you another piece to work with. $\endgroup$
    – Arthur
    Oct 22, 2019 at 15:38
  • $\begingroup$ @Arthur can you elaborate? $\endgroup$
    – Zevias
    Oct 22, 2019 at 15:40
  • $\begingroup$ @Zevias Read the definition of $O$ one more time. You will see that $f(x)\in O(2^x)$ doesn't mean $f(x)\leq 2^x$. It means something a little different. And that little extra is exactly what you need to finish the proof here. Also, $2^x+x^2\leq |2^x|+|x^2|\leq 2^x+x^2$ looks a bit unnecessary. $\endgroup$
    – Arthur
    Oct 22, 2019 at 16:13
  • $\begingroup$ @Arthur I still am not sure what to do. I reduced it further to 2 2^x so that means f(x) is O(2^x) with witness C = 2 and witness K = (-infinite, +infinity)? $\endgroup$
    – Zevias
    Oct 22, 2019 at 16:50

1 Answer 1

1
$\begingroup$

Following the definition, can you find constants $M$ and $C$ such that for all $x>M$,

$$2^x+x^2< C\,2^x\text{ ?}$$

In other words,

$$1+x^22^{-x}< C.$$

By a quick study of the function $1+x^2e^{-x}$, we see that it is decreasing for $M\ge3$. As the value at $3$ is $1+\dfrac98$, we have for instance

$$x>3\implies 2^x+x^2\ge3\cdot2^x.$$

We illustrate this on the plot below, where the vertical axis is logarithmic:

enter image description here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .