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)})$
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Please check if the correction is what is intended. $\endgroup$– SarvottamanandaMar 11, 2016 at 13:45
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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$.
answered Mar 11, 2016 at 12:43
$\begingroup$
$\endgroup$
1
If you want asymptotically positive functions check $f(n)={1 \over n}$ and $g(n)=2$
-
$\begingroup$ 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$ $\endgroup$– user777Jul 3, 2020 at 11:41