Does the fact that $f(n)$ is not $o(g(n))$ and $f(n)$ is not $\omega(g(n))$ imply that $f(n)$ is $\Theta(g(n))$?

Question

Is this statement true? $$f(n) \notin o(g(n))~~~\wedge~~~f(n) \notin \omega(g(n))~~\implies f(n)\in\Theta(g(n))$$

I'm thinking that because $f(n)$ is never greater than or less than $cg(n)$, then it must be growing at the same rate? However I don't know how to derive this solution from first principles.

what's your definition of those 3 simbols? (If it's what I have in mind, then it's false, since $f(n)=sin (n)$ and $g(n)=1$ are not comparable) — Exodd, Sep 28 '15 at 22:25

score 1 · Answer 1 · answered Sep 28 '15 at 22:27

1

In general, not every two functions are comparable asymptotically. Consider $f(x) = e^{x\cos(x)}$ and $g(x) = x$.

answered Sep 28 '15 at 22:27

Cain

1,358

Does the fact that $f(n)$ is not $o(g(n))$ and $f(n)$ is not $\omega(g(n))$ imply that $f(n)$ is $\Theta(g(n))$?

1 Answers1