Kindly give an example of positive functions f(n) and g(n) such that f(n) = O(g(n))
but it does not hold that 2^f(n) = O(2^g(n)).
A friend asked this question as this came in one of his exams. I have rattled my mind and couldnt figure out what this could be. It has to be some kind of log function I presume.
Thank you!
Actually, you don't even need logarithms. Consider $f(n) = 2n$ and $g(n) = n$.
Then, $2^{f(n)} = 2^{2n} = 4^n$ but $2^{g(n)} = 2^n$. Can you show that $2^{f(n)}$ is not $O(2^{g(n)})$?