I need help proving that if f(n) = O(g(n)) implies 2^(f(n)) = O(2^g(n)))

Question

In a previous problem, I showed (hopefully correctly) that f(n) = O(g(n)) implies lg(f(n)) = O(lg(g(n))) with sufficient conditions (e.g., lg(g(n)) >= 1, f(n) >= 1, and sufficiently large n).

Now, I need to prove OR disprove that f(n) = O(g(n)) implies 2^(f(n)) = O(2^g(n))). Intuitively, this makes sense, so I figured I could prove it with help from the previous theorem. I noticed that f(n) can be rewritten as lg(2^f(n)) and that g(n) is just lg(2^g(n)), which got me excited...this is taking the log base 2 of both sides of what I want to prove, and it simplifies things a lot!

But I'm pretty sure this won't work. Just because lg(2^f(n)) = O(lg(2^g(n))) does not necessarily mean that 2^f(n) = O(2^g(n))...that's backwards from the previous theorem (which said "implies", not "if and only if").

Do I need to try this proof another way, or can I actually go off of what I have (at least as a starter)?

**Speaking of other ways, maybe I could just argue about how raising 2 to some g(n) that is "above" an f(n) will still keep it higher? It almost feels like a common sense argument, but maybe I'm missing something important..

**Oh, oops! I forgot to add that f(n) and g(n) are asymptotically positive. By our textbook definition, this means that they are "positive for all sufficiently large n."

Answer 1

For any f,g: N->R*, if f(n) = O(g(n)) then 2^(f(n) = O(2^g(n)) (1)

We can disprove (1) by finding a counter-example.

Suppose (1) is true -> by Big-O definition, there exists c>0 and integer m >= 0 such that:

2^f(n) <= c2^g(n) , for all n >= m (2)

Select f(n) = 2n, g(n) = n, we also have f(n) = O(g(n)), apply them to (2).

-> 2^(2n) <= c2^n -> 2^n <= c (3)

This means: there exists c>0 and integer m >= 0 such that: 2^n <= c , for all n >= m.

There is no such c, because if there is, we always find n > lg(c) that makes (3) not true: 2^n >= c, for all n >= lg(c).

Therefore, (1) cannot be true.

Answer 2

If f(n) = O(g(n)),
2^(f(n)) not equal to O(2^g(n)))

Let, f(n) = 2log n and g(n) = log n
(Assume log is to the base 2)

We know, 2log n <= c(log n) therefore f(n) = O(g(n))

2^(f(n)) = 2^log n^2 = n^2
2^(g(n)) = 2^log n = n

We know that
n^2 is not O(n)

Therefore, 2^(f(n)) not equal to O(2^g(n)))

Answer 3

Well, it's not even true to begin with.

Let's say algorithm A takes 2n steps, and algorithm B takes n steps. Then their ratio is a constant.

But the ratio of 2²ⁿ and 2ⁿ is not a constant, so what you said doesn't hold.