In the question, we are to assume that f(n) is O(g(n)). Next, we have to decide whether 2^f(n) is O(2^g(n)). According, to some solutions on the internet, this can be proven to be false if we take f(n)=2n and g(n)=n. However, I'm not able to completely derive the proof to backup the premise that it is false.
Here's what I have thus far: Suppose we take f(n)=2n and g(n)=n. We know that f(n)≤ C*g(n) for C>0 and ∀ n≥n0≥0. After substituting and raising both sides to base 2, we get: 2^(2n)≤2^(c*n)≡4^n≤2^(c*n)...
Here's where I'm stuck. What I'm trying to do is as follows: for all n0 and C, I'm trying to find an n>=n0 such that 2^f(n) > 2^(c*g(n)). How should I proceed?