The following statements are equivalent:1 f ∈ Ω(g )2 g ∈ O(f )Proof. → Exercise

Para demostrar que las dos afirmaciones son equivalentes, debemos mostrar que cada una implica a la otra.

1. Supongamos que $f \in \Omega(g)$. Por definición, esto significa que existen constantes positivas $c$ y $n_0$ tales que para todo $n \geq n_0$, se cumple que $f(n) \geq c \cdot g(n)$.

2. Queremos demostrar que $g \in O(f)$. Por definición, esto significa que existen constantes positivas $C$ y $N_0$ tales que para todo $n \geq N_0$, se cumple que $g(n) \leq C \cdot f(n)$.

Dado que $f \in \Omega(g)$, tenemos $f(n) \geq c \cdot g(n)$ para $n \geq n_0$. Podemos reescribir esta desigualdad como $g(n) \leq \frac{1}{c} \cdot f(n)$. Si tomamos $C = \frac{1}{c}$ y $N_0 = n_0$, obtenemos que $g(n) \leq C \cdot f(n)$ para $n \geq N_0$. Por lo tanto, $g \in O(f)$.

Ahora, supongamos que $g \in O(f)$. Por definición, esto significa que existen constantes positivas $C$ y $N_0$ tales que para todo $n \geq N_0$, se cumple que $g(n) \leq C \cdot f(n)$.

Queremos demostrar que $f \in \Omega(g)$. Dado que $g \in O(f)$, tenemos $g(n) \leq C \cdot f(n)$ para $n \geq N_0$. Podemos reescribir esta desigualdad como $f(n) \geq \frac{1}{C} \cdot g(n)$. Si tomamos $c = \frac{1}{C}$ y $n_0 = N_0$, obtenemos que $f(n) \geq c \cdot g(n)$ para $n \geq n_0$. Por lo tanto, $f \in \Omega(g)$.

Hemos demostrado que $f \in \Omega(g)$ implica $g \in O(f)$ y que $g \in O(f)$ implica $f \in \Omega(g)$. Por lo tanto, las dos afirmaciones son equivalentes.