1

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?

Collin
  • 405

1 Answers1

3

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

Karl Winsor
  • 173
  • I forgot about these. Disregarding the cases where none of the relationships are satisfied, is my original assumption true? – Collin Aug 28 '14 at 18:15
  • Still not quite. Your statement that $f \in O(g)$ and $f \notin o(g)$ implies $f \in \Theta(g)$ is false. Consider $f, g$ defined on the natural numbers as follows. $f(n) = 0$ if $n$ is even, and $f(n) = n$ if $n$ is odd, and $g(n) = n$ for all $n$. – Karl Winsor Aug 28 '14 at 18:23
  • @KarlWinsor: I'm not sure I agree with your examples. Clearly $0 \leq f(x) \leq 2 =O(1) \ \forall x >0$ – Alex Aug 28 '14 at 18:59
  • @Alex:How do you find $f(x)\leq2$ for all $x>0$ when $f(2n+1)=2n+1$ for all $n\in\Bbb N$? – Clayton Aug 28 '14 at 19:51
  • $f(n) \leq 1 \cdot g(n)$ for all $n$, $f(n) = g(n)$ for infinitely many $n$, and $f(n) < c \cdot g(n)$ for all $c > 0$ for infinitely many $n$. This should justify my examples. – Karl Winsor Aug 28 '14 at 20:34