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


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

\ppart 
$f(x)^2 = O(g(x)^2)$

\solution{This equation holds.  Since $f(x) = O(g(x))$,
\[
\exists x_0,c\; \forall x \geq x_0, \abs{f(x)} \leq c\abs{g(x)}.
\]
So, $\forall x \geq x_0\, [f(x)^2 \leq c^2g(x)^2]$.  Therefore, there
exist $x_0' \eqdef x_0$ and $c' \eqdef c^2$ such that $\forall x \geq
x_0'\, [f(x)^2 \leq c'g(x)^2]$.  So $f(x)^2 = O(g(x)^2)$.}

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

\solution{This equation does not hold.  Let $f(x) \eqdef 2x$ and $g(x)
\eqdef 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, $4^x/2^x = 2^x$, so the
ratio grows without bound as $x$ grows---it is not bounded by a constant.}

\eparts
\end{problem}