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.

Let $f(n)=o(g(n))$. By definition there exists $n_0$ so that for all $n>n_0$ it holds that $\varepsilon \cdot g(n) \geq f(n)$ for $\varepsilon>0$ however small.

So, in plain language, starting from a certain point, $g(n)$ grows significantly faster than $f(n)$. However, how about the part before asymptotic behaviour kicks in, when $f(n)$ and $g(n)$ can go wild?

Is it possible that for some $x\in[0..n_0]$, $f(x)=M$ gets a maximal value so that $g(n) < M$ (for all $n$)?

share|improve this question
    
Whoops, I mixed up f and g :) –  Ilya Jan 28 '13 at 2:49
    
I don't really understand the question after "However". Can you explain? –  GYC Jan 28 '13 at 2:56
    
I've updated the question. I hope I'm not too confused. –  Ilya Jan 28 '13 at 3:05
add comment

2 Answers

up vote 1 down vote accepted

Yes for example, $f(x) = \frac{1}{x}$ defined on $[\frac{1}{2},\infty)$ is $o(1)$ and $\forall x \in [\frac{1}{2},1): \frac{1}{x} > 1$, and $f(x)$ reaches maximal value: $2$.

share|improve this answer
    
Thanks! This helps. –  Ilya Jan 28 '13 at 3:14
add comment

I think you are confused. The little $o$ notation just means $|\frac{f(n)}{g(n)}|<\epsilon$ for any $\epsilon>0$ if $n$ is large enough. So it is totally possible that for some $n$ value $f(n)\ge g(n)$. For example $\sin[1/x]=o(x^{2})$.

share|improve this answer
    
What I meant is that not only f(n) >= g(n) for some n, but f(n)=M so that g(n)<=M and g(x)<=M for all x. –  Ilya Jan 28 '13 at 3:11
    
I see. Updated. Hopefully you can figure it out. –  Bombyx mori Jan 28 '13 at 3:17
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.