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
    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.

  • 0
    @Didier: At least, you have to admit the question of $0 \in o(0)$ is very much an edge case. :p2012-03-11