Properties that hold when $f = \mathcal{O}(g)$ This is a homework problem. There are two questions where the answers seem intuitive, but even if I were correct in assuming they were true, I'd still need to provide a proof:
When $f(n) = \mathcal{O}(g(n))$, do these two statements hold true:
$$2^{f(n)} = \mathcal{O}(2^{g(n)})$$
and
$$f(n)^2 = \mathcal{O}(g(n)^2)$$
Both answers seem intuitive: if $f$ grows faster than $g$, then increasing the rate at which the functions increase wouldn't seem to change the relationship. Am I correct, and if so, how does one go about proving something like this?
 A: For the first problem, let $f(n)=2n$ and $g(n)=n$. Then certainly $f(n)=O(g(n))$. But $2^{f(n)}$ is not $O(2^{g(n)})$: it grows far faster.
For a proof, it is enough  to show that $\frac{2^{2n}}{2^n}$ blows up as $n\to\infty$.  This is not hard. The counterexample shows that $f(n)=O(g(n))$ does not imply that $2^{f(n)}=O(2^{g(n)})$. 
For the second problem, you know that there is a positive constant $k$ such that for large enough $n$, we have $f(n)\lt kg(n)$. Now you need to show that there is a positive constant $l$ such that for large enough $n$, we have $(f(n))^2 \lt l(g(n))^2$. This should not be difficult. 
A: As Andre points out, the first statement is certainly untrue.  As another counterexample, consider
$$
f(n)=2\log_2(n) = \log_2(n^2), \quad g(n) = \log_2(n), \quad 
$$
Here, we note $2^{f(n)} = n^2$ is not $O(2^{g(n)}) = O(n)$.
As for proving that second statement, use the definition:
Suppose that $f(n) = O(g(n))$.  That is, there is a $K>0$ so that
$$
|f(n)| \leq K|g(n)|
$$
Whenever $n$ is bigger than some $n_0$.  Squaring both sides, it follows that
$$
|f(n)^2| \leq K^2|g(n)|^2
$$
Whenever $n$ is bigger than that same $n_0$.  Why does this show that $[f(n)]^2 = O([g(n)]^2)$?
