Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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!

share|improve this question
1  
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

2 Answers 2

up vote 13 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.