3
$\begingroup$

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

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

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

If you want asymptotically positive functions check $f(n)={1 \over n}$ and $g(n)=2$

| cite | improve this answer | |
$\endgroup$
  • $\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$ – user777 Jul 3 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.