-1

I can't find a counter example to this formula, or in case if its true - what is the correct way to prove it... In this case, first o is "little-o notation" - a strict upper bound. And second is "big-O notation".

I found here fine examples, that this statements not true

"$f(n) = o(g(n)) => 2^{f(n)} = o(2^{g(n)})$", with counter example f(n)=1/n, g(n)=1.

"$f(n) = O(g(n)) => 2^{f(n)} = O(2^{g(n)})$", with counter example f(n)=n, g(n)=2n.

I'm looking for a way to prove or disproove this expression exactly:

$f(n) = o(g(n)) => 2^{f(n)} = O(2^{g(n)})$

Jaroslav
  • 9
  • What have you tried? Giving some examples for related problems is not really a serious attempt at a proof. Have you tried applying the definition of $f(n)=o(g(n))$? – Qudit Nov 22 '17 at 23:19
  • yes i tried apply definition... for little-o, lim n->infty f(n)/g(n) = 0, but it tell me nothing... to compare with big Oh... f(n) =< cg(n) – Jaroslav Nov 22 '17 at 23:28

1 Answers1

1

If $f(n) = o(g(n))$, then $$ f(n)/g(n)\to 0. $$ as $n\to\infty$. In particular, for every $\varepsilon>0$ there exists $N$ such that for $n\geq N$, $f(n)<\varepsilon g(n)$ (here we suppose that the sequences are positive or eventually positive). Take $\varepsilon=1$. What can we say about $2^{f(n)}$.

Sri-Amirthan Theivendran
  • 31,116