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