I'm trying to prove that for arbitrary $c > 0$,

$f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$

Intuitively, this seems to be true to me (little-o implies some gap "between" $f(n)$ and $n^c$ that we can formally express as $\epsilon$). However, I'm having some trouble formalising this argument.

What I've done so far:

$f(n) = o(n^c) \rightarrow \exists c_0, n_0 > 0 \ s.t. \forall n \geq n_0, 0 \leq f(n) < c_0 n^c$

Suppose (for a contradiction) that no such $\epsilon$ fulfilling the above condition exists.

Then we have

$\forall \epsilon > 0, \exists n \geq n_0 \ s.t. f(n) \geq c_0 n^{c-\epsilon}$

I'm not sure how to proceed from here.

  • $\begingroup$ what does s.t. stand for $\endgroup$ – shi95 May 19 '19 at 8:29

This is false. Consider for example $$ f(n) = \frac{n^c}{\log n}. $$

  • $\begingroup$ Thank you for your counterexample! If I may ask, how did you come up with this counterexample? (Your thought process, etc.) $\endgroup$ – John Doe Jan 28 '19 at 8:39
  • 3
    $\begingroup$ @JohnDoe $\log n$ is a well-known example of a "slowly" diverging function which is $O(n^\epsilon)$ for any $\epsilon>0$. Note that $\log$ is a well-known function, so it helps knowing its properties, including its asymptotic behavior. Once one knows this, it's easy to adapt it to your case. $\endgroup$ – chi Jan 28 '19 at 9:38

Yuval's counterexample $f(n)=\dfrac{n^c}{\log n}$ shows that there may not exist $\epsilon > 0$ such that $f(n) = O(n^{c-\epsilon})$ although $f(n) = o(n^c)$.

In fact, there is a general proposition.

(Gap between $o$ and $O$). Let $f_\epsilon(n)$ be a nondecreasing positive function on $\Bbb N$ parameterized by $\epsilon\ge0$ such that $f_{\epsilon_1}(n)\ge f_{\epsilon_2}(n)$ and $f_{\epsilon_2}(n)=o(f_{\epsilon_1}(n))$ if $\epsilon_1<\epsilon_2$. In plain words, $f_\epsilon(n)$ becomes bigger when $\epsilon$ becomes smaller. Then there exists a function $f(n)$ such that $f(n)=o(f_0(n))$ and $f(n)\not=O(f_\beta(n))$ for any $\beta>0$.

Proof. Let $k>0$ be an integer. Since $f_{\frac1k}(n)=o(f_{\frac1{k+1}}(n))$ and $f_{\frac1k}(n)=o(f_0(n))$, there exists constant $c_k>0$ such that $f_{\frac1{k}}(n)\le \frac1k(f_{\frac1{k+1}}(n))$ and $f_{\frac1{k}}(n)\le \frac1k(f_0(n))$ if $n>c_k$. We can assume $c_k\lt c_{k+1}$; otherwise, we can replace $c_{k+1}$ by $\max(c_k+1, c_{k+1})$ recursively.

Let $f(n)$ be defined as the following. $$f(n) = f_{\frac1k}(n) \text{ when }c_k\le n\lt c_{k+1}.$$

We can verify that $f(n)=o(f_0(n))$ and $f(n)\not=O(f_\epsilon(n))$ for any $\epsilon>0$.

Here are a few related exercises.

Exercise 1. Show that $\log n=o(n^\epsilon)$ for any $\epsilon >0$.

Exercise 2. Show that $n=o(e^{\epsilon n})$ for any $\epsilon >0$.

Exercise 3. Show that $n=o(e^{\epsilon n^c})$ for any $\epsilon >0$ and $c\gt 0$.


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.