# 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?

## 2 Answers

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.

• Thanks for your answer. In the course that I am taking, our professor has said that, for example 2^n = O(3^n), even though 3^n/2^n as n->infinity is infinity, which seems to differ from the answers here and also every source I look up. Note that this is a course mostly relating to algorithms (and, right now, time complexity). Does that at all change how to look at this problem?
– ಠ_ಠ
Commented Jan 28, 2014 at 5:18
• Your professor is right, certainly $2^n$ is $O(3^n)$. We can take the constant to be $1$. The ratio $\frac{f(n)}{g(n)}$ goes to $0$, which is very good. But in my counterexample, the ratio $\frac{2^{2n}}{2^n}$ goes to infinity, which is a very different matter. No change at all in the answer, I gave it as if it were a question on complexity. Commented Jan 28, 2014 at 5:22
• Thanks. Mental block on my part, your answer cleared things up a lot
– ಠ_ಠ
Commented Jan 28, 2014 at 5:37
• You are welcome. One has to make the mistakes to get inoculated against them. Commented Jan 28, 2014 at 5:42

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