Properties that hold when $f = \mathcal{O}(g)$

Question

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?

Answer 1

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.

Answer 2

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)$?