Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that some function $f(n)$ is in $o(n)$. Is it fomally correct to say that there exists an $N$ such that for all $n \ge N$ it holds that $$f(n) \le \frac{c n}{g(n)}$$ where $c>0$ is a constant and $g(n)$ is a strictly increasing function of $n$ ? My reasoning is that $f(n) \in o(n)$ implies that $\lim_{n\rightarrow\infty} \frac{f(n)}{n} = 0$, so the above should follow directly from $f(n) \in o(n)$, right?

share|improve this question
1  
Try $g(n) = (1 - 1/n) \inf \{k / f(k) : k \geq n\}$ (unless $g$ is identically equal to 0 starting from some $N$). –  Yury Jul 15 '12 at 16:32
    
Just to be clear: you want to prove that there is at least one such $g(n)$? –  bartgol Jul 15 '12 at 16:33
    
@bartgol: yes exactly. –  somebody Jul 15 '12 at 16:37
add comment

1 Answer

up vote 3 down vote accepted

You can reformulate your question as: is it true that if $f(n)\to 0$, then there is an increasing function $g(n)$ such that for $n$ large enough $f(n)\leq c/g(n)$? I think the answer to this question is positive. As Yury pointed out, it should be enough to take $$g(n)=h(n)\text{inf}\left\{\frac{1}{f(k)},k\geq n\right\}$$ where $h(n)$ is any positive increasing function smaller than one.

share|improve this answer
1  
Technically it should be $|f(k)|$ rather than $f(k)$, since $f(n)$ was not specified to be positive. Indeed, not only is your $g(n)$ increasing, it increases to infinity. By adding this clause, the condition becomes exactly equivalent to $f(n) = o(n)$. –  Erick Wong Jul 15 '12 at 17:05
    
You're right, there should be an absolute value there. –  bartgol Jul 16 '12 at 18:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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