0
$\begingroup$

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.

  • 0
    Every $f$ and $g$ such that $f(n)=g(n)$ for every $n$ fulfill the condition written **in your post**.2011-11-11
  • 0
    I have tagged it as computer-science + asymptotics, based on the previous tag and the "computer-sciency" "definitions"...2012-02-09

1 Answers 1

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.

  • 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.2011-11-11
  • 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)$).2011-11-13
  • 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](http://en.wikipedia.org/wiki/Big_O_notation)?2011-11-13
  • 0
    @Didier: At least, you have to admit the question of $0 \in o(0)$ is very much an edge case. :p2012-03-11