AALIE

Relaciones entre las 6 notaciones

Implicaciones entre las seis notaciones y guía práctica para escoger la notación adecuada.

6. Relaciones entre las 6 notaciones

Las notaciones no son independientes; se relacionan así:

f \sim g \Rightarrow f \in Θ (g) \Rightarrow (f \in O (g) \land f \in Ω (g))

f \in o (g) \Rightarrow f \in O (g), pero f \in / Θ (g)

f \in ω (g) \Rightarrow f \in Ω (g), pero f \in / Θ (g)

Diagrama de inclusión entre notaciones

Renderizando diagrama...

Dicho de forma sencilla

$\sim$ es la más exigente: implica todo lo demás ( $Θ$ , $O$ , $Ω$ ).
$Θ$ es la segunda más exigente: implica $O$ y $Ω$ , pero no implica $\sim$ .
$O$ solo acota por arriba; $Ω$ solo acota por abajo. Son "medias verdades" por separado.
$o$ y $ω$ son las más restrictivas en su sentido: excluyen la igualdad, por eso una función no puede pertenecer a $o (g)$ y a $Θ (g)$ al mismo tiempo.

Cuidado

No confundas una implicación con una equivalencia. Que $f \in o (g)$ implique $f \in O (g)$ no significa que toda función en $O (g)$ también esté en $o (g)$ . La dirección importa.

¿Cuál usar en cada situación?

La siguiente tabla resume qué notación conviene usar según la situación de análisis.

Notación recomendada según la situación

Situación	Notación recomendada
Análisis del mejor caso (comportamiento exacto)	$Θ$ (theta) — cota exacta
Análisis del peor caso (sin saber si la cota es ajustada)	$O$ (big-O)
Análisis del peor caso con cota exacta demostrada	$Θ$ especificando "en el peor caso"
Análisis del caso promedio (siempre exacto)	$Θ$ siempre
Comparar que f es estrictamente menor orden que g	$o$ (little-o)
Comparar que f es estrictamente mayor orden que g	$ω$ (little-omega)
Demostrar que f y g son casi idénticas (misma constante principal)	$\sim$ (tilde)

Peor caso: no mezclar O con Θ sin justificación

Para peor caso puedes usar $O$ cuando solo tienes una cota superior. Usa $Θ$ en el peor caso únicamente cuando la cota exacta ya está demostrada.

Caso promedio

El caso promedio se reporta cómo $Θ$ porque representa un comportamiento esperado exacto bajo el modelo probabilístico definido.