1
$\begingroup$

I can't find a counterexample to $$f(n) = o(g(n)) \text{ implies } 2^{f(n)} = o(2^{g(n)})\,,$$ but I do not know a formal way of proving it. Can anyone lead me in the right direction? I asked this exact question yesterday in Stack Overflow by accident (meant to post here) but no one could come up with a valid way of approaching this question.

This is "little-$o$" notation by the way. So a strict upper bound It should be for monotonically increasing functions

$\endgroup$
3
$\begingroup$

Hint:

We want to prove $2^{f(n)} = o(2^{g(n)})$. This is equivalent to $\lim_{n\to\infty} \dfrac{2^{f(n)}}{2^{g(n)}} = 0$. We can rewrite the expression inside the limit as $2^{f(n)-g(n)}$, and, exploiting the hypothesis $f(n) = o(g(n))$, we have $\lim_{n\to\infty} f(n)-g(n) = \cdots$

$\endgroup$
1
$\begingroup$

Firstly, let's establish the definition for little-o:

$f(n) = o(g(n))$ if and only if $\lim\limits_{n \to \infty} \frac{f(n)}{g(n)} = 0$

  • Firstly, about counterexample. Take $f(n) = \frac{1}{n^2}$ and $g(n) = \frac{1}{n}$. The ratio is $\frac{f(n)}{g(n)} = \frac{\frac{1}{n^2}}{\frac{1}{n}} = \frac{1}{n} \to 0$, so $f(n) = o(g(n))$. However, $\frac{2^{f(n)}}{2^{g(n)}} = 2^{f(n) - g(n)} = 2^{\left(\frac{1}{n^2} - \frac{1}{n}\right)} \to 1$, because $\frac{1}{n^2} - \frac{1}{n} \to 0$ when $n \to \infty$, so the conclusion given is not correct.
  • Secondly, let's see the formality so we know from where this counterexample comes and what additional conditions might support the claim.

Recall, that if $\lim\limits_{n \to \infty} \frac{f(n)}{g(n)} = 0$ then by definition of the limit $\forall \epsilon > 0 \exists N\forall n \geq N : \left|\frac{f(n)}{g(n)}\right| \leq \epsilon$. From this immediately we get $\left|{f(n)}\right| \leq \epsilon\left|{g(n)}\right|$. After subtracting $g(n)$ and adding for example positiveness (don't want to dig into all cases) we get something like $f(n) - g(n) \leq (\epsilon-1) g(n)$. The conclusion I have taken from here is that the claim might be true only if $g(n) \to \infty$. And that's exactly from where I took the counterexample.

Update 1

For those who ask what about monotonicity: Still take $g(n)$ any function with limit not infinity, for example $\arctan(x)$, $f(n) = \frac{g(n)}{n}$. By definition $f(n) = o(g(n))$. The difference $f(n) - g(n) \to 0 - \frac{\pi}{2} \neq -\infty$ so powers are not related as little-o.

Update 2

For both increasing $f$ and $g$ you can revert the counterexample $f(n) = -1/n^2$ and $g(n) = -1/n$.

If you put the requirement, that starting from some $n$ we have $f(n) > 0$ and $g(n) > 0$, the following is true. Assume $g(n) \not\to \infty$, that is $g(n) \to C \geq 0$. Then $f(n) = \alpha_n g(n)$ where $\alpha_n \to 0$ so $f(n) \to 0$. But $f(n) > 0$ and thus must be decreasing at some point which violates the monotinicity requirement. By contradiction, $g(n) \to \infty$.

Take $\epsilon = \frac{1}{2}$ in the above, you have $f(n) - g(n) \leq -0.5 g(n) \to -\infty$ which proofs the claim.

$\endgroup$
  • 4
    $\begingroup$ The OP mentioned monotonically increasing functions. $\endgroup$ – Willard Zhan Feb 20 '17 at 6:51
  • $\begingroup$ @WillardZhan please see the obvious update $\endgroup$ – Eugene Feb 20 '17 at 7:21
  • 2
    $\begingroup$ No, here $f$ is still not increasing. Actually for $f,g$ both monotone increasing, the implication is correct. $\endgroup$ – Willard Zhan Feb 20 '17 at 7:43
  • $\begingroup$ @WillardZhan use $f(n) = -1/n^2$ and $g(n) = -1/n$. If you add positiveness $g(n) \to \infty$ $\endgroup$ – Eugene Feb 20 '17 at 9:17
  • $\begingroup$ $(\arctan x)/x$ isn't monotone increasing. $\endgroup$ – David Richerby Feb 20 '17 at 9:43

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.