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.

From definition of $o$ and $\omega$

one states that $0 < c_1\cdot g(n) < f(n)$ for $n > n_0$ and some $c_1$ and another states that $0 < f(n) < c_2\cdot g(n)$ for $n > n_1$ and some $c_2$

It seems like there is no such function that satisfies condition. But i can't show this rigorously.

share|improve this question
    
Every $f$ and $g$ such that $f(n)=g(n)$ for every $n$ fulfill the condition written in your post. –  Did Nov 11 '11 at 18:36
    
I have tagged it as computer-science + asymptotics, based on the previous tag and the "computer-sciency" "definitions"... –  Aryabhata Feb 9 '12 at 23:00
add comment

1 Answer 1

Note, that the definition of $\omega(g)$ says (assuming you refer to ordinary landau notation, in which case you did not look up the definitions correctly): For every $c_1>0$, there is a $n_1$, such that for all $n > n_1$ we have $0 < c_1|g(n)| < |f(n)|$. $o(g)$ is defined similar.

For $c_1 = 2$ and $c_2 = 1$ a function $f \in \omega(g) \cap o(g)$ must satisfy $2|g(n)| < |f(n)| < |g(n)|$ for all $n > n_0$ and some $n_0$, which is clearly impossible.

share|improve this answer
1  
Actually, there is a counterexample to this: if $g(n)=0$ for every $n$ large enough, then $g(n)=o(g(n))$ and $g(n)=\omega(g(n))$ hence $o(g)\cap\omega(g)$ is not empty. –  Did Nov 11 '11 at 20:59
1  
@Didier Piau: In the definition given above this is not true. Also most definitions of $o$ and $\omega$ satisfy $f \not\in o(f)$ (or $f \not\in \omega(f)$). –  Alexander Thumm Nov 13 '11 at 17:47
2  
If you refer to the fact that your definitions ill-advisedly use strict inequalities, I agree. But then some $f$ are not in $\omega(f)$ and some $\omega(g)$ are empty, which is strange, and which explains why everybody uses large inequalities. Then, as I wrote, $f\in\omega(f)$ for every $f$ and $f\in o(f)$ for some $f$ (these are not and should not be matters of convention, pace your comment). By the way, to write that *most definitions of $\omega$ satisfy $f\notin\omega(f)$* for every $f$ is... well, somewhat creative. Any reference? –  Did Nov 13 '11 at 18:03
    
@Didier: At least, you have to admit the question of $0 \in o(0)$ is very much an edge case. :p –  Hurkyl Mar 11 '12 at 0:19
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.