\problemdata      
        {asymptotics-3} % latex-friendly label for the prob.
        {Asymptotics} % The topic(s) of the problem content.
        {F00 TU7} % Source (if known)
        {S02 CP6F} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).

\begin{problem} 
Given that $f(x) = O(g(x))$, prove or disprove the following: 
\begin{problemparts}

\problempart
$2^{f(x)} = O(2^{g(x)})$.

\solution{
The above does not hold. Let $f(x) = 2x$ and $g(x) = x$. Then $f(x)
= O(g(x))$. Now $2^{f(x)} = 2^{2x} = 4^x$, and $2^{g(x)} = 2^x$, and
$4^x\neq O(2^x)$. Indeed,
\[
\frac{4^x}{2^x} = 2^x,
\] so the ratio
grows without bound as $x$ grows---it is not bounded by a constant.
}

\problempart 
$f(x)^2 = O(g(x)^2)$.

\solution{%
The above does hold.  Since $f(x) = O(g(x))$, there exist $x_0$, $c$
such that for all $x \geq x_0$, $|f(x)| \leq c g(x)$.  So, for all 
$x\geq x_0$,  $|f(x)|^2 \leq c^2g(x)^2$.  Therefore, there exist 
$x_0' = x_0$ and $c' = c^2$ such that for all $x \geq x_0'$, 
$|f(x)^2| \leq c'g(x)^2$.  So $f(x)^2 = O(g(x)^2)$. 
}
\end{problemparts}
\end{problem}
