Do small o, small omega, and big theta cover all relationships between two functions

1.5k Views Asked by At

Given any two functions $f(n)$ and $g(n)$ is one of these three statements always true:

$f(n) \in o(g(n))$

$f(n) \in \omega(g(n))$

$f(n) \in \Theta(g(n))$

Logically, this makes sense to me. For a homework assignment I'm given various functions $f(n)$ and $g(n)$ and asked to determine whether they are $o$, $\mathcal{O}$, $\omega$, $\Omega$, or $\Theta$ of eachother.

In the case where a function is $\mathcal{O}$ but not $o$, it must be $\Theta$. And in the case where a function is $\Omega$ but not $\omega$ it must also be $\Theta$.

Am I missing anything logically?

1

There are 1 best solutions below

5
On BEST ANSWER

There are many examples of functions that do not satisfy any of the relationships you gave. (big-Oh, little-oh, big-Omega, little-omega, or big-Theta).

For instance, $f(x) = 1 + sin(x)$ and $g(x) = 1 + cos(x)$.