If $f(n)=O(g(n))$, when is $2^{f(n)}=O(2^{g(n)})$?

Question

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

Answer 1

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.)

Answer 2

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.