Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 3

Problem:

Assume again two (positive) nondecreasing functions $f$ and $g$ such that $f(n)=O(g(n))$. Is $2^{f(n)}=O(2^{g(n)})$ ?

Solution:

Not really, let us check some simple special case.

Case 1: $f(n) = g(n) = n$. In this case, it $2^n = O(2^n)$ is certainly true.
Case 2: $f(n) = 10n, g(n) = n$. In this case, we have $2^{10n} \neq O(2^n)$.

To understand case 2, suppose the contrary, there would exists integers $c$ and $n_0$ such that $2^{10n} \leq c2^n$, but then $2^{9n} \leq c$ which is absurd.

With that, we can be sure that:

The statement is not always true.
The statement is not always false.

What is the necessary condition for the statement to be true?

Consider the very same proof above, what we really want is that instead of the statement being absurd, we want it to be true for sure, so we have

$2^{f(n)} \leq c2^{g(n)}$, leading to $2^{f(n) - g(n)} \leq c$. We can be sure that will be true if $f(n) - g(n) \leq 0$, or in other words, $f(n) \leq g(n)$.