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

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.

• what does s.t. stand for – shi95 May 19 at 8:29

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

• Thank you for your counterexample! If I may ask, how did you come up with this counterexample? (Your thought process, etc.) – John Doe Jan 28 at 8:39
• @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. – chi Jan 28 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$$.