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

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 22n and 2n is not a constant, so what you said doesn't hold.


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