# Is $O$ in $f \in O(g)$ a total partial order on the set of functions?

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!

-
The answers have shown this to be false, but I wonder, what if we add a constraint such as restricting to increasing functions? – Harry Altman Apr 27 '11 at 0:36
@Harry Altman: You still won't have anti-symmetry: $2x=O(x)$, $x=O(2x)$, but $x\neq 2x$. – Rasmus May 16 '11 at 20:39
Well, yes, but that's obvious. I'm wondering about totality. – Harry Altman May 16 '11 at 21:36

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

-

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}$

-