¿Es $O$ en $f \in O(g)$ un orden parcial total en el conjunto de funciones?

Question

1. Dado el conjunto de funciones definidas en un subconjunto de $\mathbb{R}$ y tomando valores en $\mathbb{R}$, me preguntaba si $O$ como en $f \in O(g)$ es un orden parcial total. ¿Por total, me gustaría saber si todas las funciones se pueden comparar por $O$? ¿Actúa como $\geq$ en $\mathbb{R}$?
2. ¿Qué hay de $\Omega$, $\Theta$, $o$, $\omega$ y $\sim$? ¿Están actuando como $\leq$, $==$, $>$, $<$ y $==$ respectivamente?

Para definiciones, vea Wikipedia. Gracias y saludos!

Answer 1

No es un orden parcial ya que no tienes antisimetría: $f\in O(g)$ y $g\in O(f)$ no implica $f=g$.

Cuando identificas funciones que son equivalentes en ese sentido, terminas con un orden parcial (la reflexividad y la transitividad son obvias), pero este no será un orden total: por ejemplo, $\sin(x)$ y $\cos(x)$ no son comparables.

En resumen, $O$ solo define una relación de preorden en el conjunto de funciones de $\mathbb R$ a $\mathbb R$.

Answer 2

Ninguno de ellos es un orden total.
Toma $f(n)=\begin{cases} n & \text{n impar}\\ n^2 &\text{n par}\end{cases}$
$g(n)=\begin{cases} n^2 & \text{n impar}\\ n &\text{n par}\end{cases}$