Where have I gone wrong in “proving” this big-O identity?

Question

(From CLRS -- 3-4,d)

Let $f(n)$ and $g(n)$ be asymptotically positive functions.

I tried to prove that $$f(n) = O(g(n)) \implies 2^{f(n)} = O\left(2^{g(n)}\right) .$$

I know that the above statement is false, so where have I gone wrong in my proof?:

Suppose $f(n) = O(g(n)).$ Then there exist positive real numbers $c, n_0$ such that for all $n \geq n_0:$ $$0 \leq f(n) \leq c g(n).$$ Raising all sides to the power of 2, we have: $$0 \leq 2^{f(n)} \leq 2^{cg(n)}$$ (we can do this because $2^n$ is an increasing function).

From this, we can say that $$0 \leq 2^{f(n)} \leq \underbrace{2^c}_{\text{arbitrary constant}}\cdot 2^{g(n)}$$ so if $d = 2^c$, we can say that $2^{f(n)} = O(2^{g(n)})$.

(I now know that $f(n) = 2n, \ \ g(n) = n$ is an easy counterexample, but I'm still struggling to find the flaw in my "proof").

Answer 1

You should be able to work out the answer yourself. Here's the general procedure:

Since you know of a counterexample to the original claim, plug those $f,g$ into each step of your proof and find the first step in your proof where the proof goes wrong. In other words, find the first claim made in the proof that isn't correct for that choice of $f,g$. That will help you pinpoint the step in your proof that is flawed, i.e., that makes a conclusion that doesn't follow logically from the previous steps.

Answer 2

Your mistake seems to be in assuming that $a^n \cdot a^m = a^{nm}$. Rather, we have $a^n \cdot a^m = a^{n + m}$.