I just wanted an example in which the equation given below is not correct.

$f(n) = o(g(n)) \Leftrightarrow 2^{f(n)} = o(2^{g(n)})$

• Please check if the correction is what is intended. – Shreesh Mar 11 '16 at 13:45

Trivially: $f(n) = 0, g(n) = 1$. Then $lim_{n \to \infty} f(n)/g(n) = lim_{n \to \infty} 0 / 1 = 0$ and $lim_{n \to \infty} 2^{f(n)}/2^{g(n)} = lim_{n \to \infty} 1 / 2 \neq 0$. You may want to think if less trivial cases exist.
Hint: $2^{f(n)} = o(2^{g(n)})$ does not always imply $f(n)=o(g(n))$.
For any monotonically increasing $f(n) = g(n)/c$, $c > 1$, $f(n) = \Theta(g(n)) \neq o(g(n))$ but $2^{g(n)} = 2^{cf(n)}$ and therefore $2^{f(n)} = o(2^{cf(n)})$.
In particular, the proposition fails for $f(n) = n$ and $g(n)=2n$.
If you want asymptotically positive functions check $f(n)={1 \over n}$ and $g(n)=2$
• it is not a counterexample: e.g. check that as n approaches $\infty$, then $\frac{1/n}{2}=0$ and $\frac{2^\frac1n}{2^2}=0$ – user777 Jul 3 at 11:41