4
$\begingroup$
  1. Given the set of functions defined on a subset in $\mathbb{R}$ and taking values in $\mathbb{R}$, I was wondering if $O$ as in $f \in O(g)$ is a total partial order? By total, I would like to know if every two functions can be compared by $O$? Is it acting like $\geq$ on $\mathbb{R}$?
  2. How about $\Omega$, $\Theta$, $o$, $\omega$ and $\sim$? Are they acting like $\leq$, $==$, $>$, $<$ and $==$ respectively?

For definitions, see Wikipedia. Thanks and regards!

  • 0
    Well, yes, but that's obvious. I'm wondering about totality.2011-05-16

2 Answers 2

13

It is not a partial order since you don't have anti-symmetry: $f\in O(g)$ and $g\in O(f)$ does not imply $f=g$.

When you identify functions which are equivalent in that sense, you end up with a partial order (reflexivity and transitivity are obvious), but this this will not be a total order: for instance, $\sin(x)$ and $\cos(x)$ are not comparable.

Summing up, $O$ only defines a preorder on the set of functions from $\mathbb R$ to $\mathbb R$.

4

None of those is a total order.
Take $f(n)=\begin{cases} n & \text{n odd}\\ n^2 &\text{n even}\end{cases}$
$g(n)=\begin{cases} n^2 & \text{n odd}\\ n &\text{n even}\end{cases}$