If $f(n)=O(g(n))$, when is $2^{f(n)}=O(2^{g(n)})$? There are questions that ask if $2^{f(n)}=O(2^{g(n)})$ is true (Big-O: If $f(n)=O(g(n))$, prove $2^{f(n)}=O(2^{(g(n)})$) and it clearly isn't for all $f$ and $g$. But I haven't found a question which discusses when the two can be equal. Is it true for $f\leq g$ for sufficiently large $n$? Because then $2^{f(n)}\leq 2^{g(n)}$ and hence $2^{f(n)}=O(2^{g(n)})$. Are there any other conditions on $f,g$?
 A: If $f(n) \in O(g(n))$, then there exists some $n_1$ and positive real constant $c_1$ such that $f(n) \leq c_1g(n)$ for all $n \geq n_1$. Assume that we've already found a solution that makes this true.
If $2^{f(n)} \in O(2^{g(n)})$, then there exists some $n_2$ and positive real constant $d$ such that $2^{f(n)} \leq d\cdot 2^{g(n)}$ for all $n \geq n_2$. This can be simplified to $2^{f(n)-g(n)} \leq d$ and then $f(n) \leq g(n) + \log_2(d)$. Let $c_2 = \log_2(d)$. Then $f(n) \leq g(n) + c_2$.
Assume that we are considering some $n \geq \max(n_1,n_2)$. So basically we are comparing $f(n) \leq c_1g(n)$ against $f(n) \leq g(n) + c_2$ for some sufficiently large $n$ and a valid $c_1$ making the first inequality hold.
Note that if $c_1 \leq 1$, then $f(n) \leq c_1g(n) \leq g(n) \leq g(n) + c_2$. In other words, it is true regardless of $c_2$. This means if $f(n) \in O(g(n))$, then $2^{f(n)} \in O(2^{g(n)})$ if $f(n) \leq g(n)$.
Otherwise, if $c_1 > 1$, then we have two cases: $f(n) \leq c_1g(n) \leq g(n) + c_2$, which is true when $c_2 \geq (c_1-1)g(n)$, or $f(n) \leq g(n) + c_2 \leq c_1g(n)$, which is true when $c_2 \leq (c_1-1)g(n)$. Either way, the value of $c_2$ depends on $g(n)$, which makes it non-constant, unless $g(n)$ is a constant function itself. But then if $g(n)$ is constant, then so is $f(n)$, since $f(n) \leq c_1g(n)$. 
Furthermore, we could also ignore $c_1$ altogether and simply pick some $c_2$ that makes $f(n) \leq g(n) + c_2$ true, which only occurs when $f(n) - g(n) \leq c_2$.
To summarize and combine cases, if $f(n) \in O(g(n))$, then $2^{f(n)} \in O(2^{g(n)})$ only when $f(n) \leq g(n)$ (for some sufficiently large $n$) and/or if $f(n)-g(n)$ is a constant.
A: You know for $n$ large enough that $f(n)\leq C_1 g(n)$ (for some constant $C_1$) and this implies that $2^{f(n)}\leq 2^{C_1 g(n)}$ for the same values of $n$.  However, what you need to show (if it is possible) is that $2^{f(n)}\leq C_2 2^{g(n)}$.  In some cases this is going to be problematic since $2^{C_1g(n)}=(2^{C_1})^{g(n)}$.  In particular, this is a problem when $C_1>1$ (especially if $f(n)=C_1 g(n)$ and $C_1>1$).
In order for the statement to be true, you need $2^{C_1}\leq 2$ and this is achieved precisely when $C_1\leq 1$.  In short, the statement is only true when $f(n)\leq g(n)$ for sufficiently large $n$.  (Also assuming that $f$ and $g$ are non-negative.)
