Propiedades de las notaciones asintóticas

Prerrequisito: notaciones asintóticas
Suponiendo que f(n), g(n) y h(n) sean funciones asintóticas, las definiciones matemáticas son:

1. Si f(n) = Θ(g(n)) , entonces existen constantes positivas c1, c2, n0 tales que 0 ≤ c1.g(n) ≤ f(n) ≤ c2.g(n) , para todo n ≥ n0
2. Si f(n) = O(g(n)) , entonces existen constantes positivas c, n0 tales que 0 ≤ f(n) ≤ cg(n) , para todo n ≥ n0
3. Si f(n) = Ω(g(n)) , entonces existen constantes positivas c, n0 tales que 0 ≤ cg(n) ≤ f(n) , para todo n ≥ n0
4. Si f(n) = o(g(n)) , entonces existen constantes positivas c, n0 tales que 0 ≤ f(n) < cg(n) , para todo n ≥ n0
5. Si f(n) = ω(g(n)) , entonces existen constantes positivas c, n0 tales que 0 ≤ cg(n) < f(n) , para todo n ≥ n0

Propiedades:

1. Reflexividad:
   Si se da f(n) entonces

   f(n) = O(f(n))

   Ejemplo:
   Si f(n) = n ³ ⇒ O(n ³ )
   De manera similar,

   f(n) = Ω(f(n)) 
   f(n) = Θ(f(n)) 

2. Simetría:

   f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n))

   Ejemplo:
   Si f(n) = n ² y g(n) = n ² entonces f(n) = Θ(n ² ) y g(n) = Θ(n ² )
   Prueba:

   • Parte necesaria:
     f(n) = Θ(g(n)) ⇒ g(n) = Θ(f(n))
     Por definición de Θ, existen constantes positivas c1, c2, no tales que c1.g(n) ) ≤ f(n) ≤ c2.g(n) para todo n ≥ no
     ⇒ g(n) ≤ (1/c1).f(n) y g(n) ≥ (1/c2).f(n)
     ⇒ (1/c2).f(n) ≤ g(n) ≤ (1/c1).f(n)
     Dado que c1 y c2 son constantes positivas, 1/c1 y 1/c2 están bien definidas. Por lo tanto, por la definición de Θ, g(n) = Θ(f(n))
   • Parte de suficiencia:
     g(n) = Θ(f(n)) ⇒ f(n) = Θ(g(n))
     Por definición de Θ, existen constantes positivas c1, c2, no tales que c1.f(n) ) ≤ g(n) ≤ c2.f(n) para todo n ≥ no
     ⇒ f(n) ≤ (1/c1).g(n) y f(n) ≥ (1/c2).g(n)
     ⇒ (1/c2).g(n) ≤ f(n) ≤ (1/c1).g(n)
     Por la definición de Theta(Θ), f(n) = Θ(g(n))
3. Transistividad:

   f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = O(h(n))

   Ejemplo:
   Si f(n) = n, g(n) = n ² y h(n) = n ³
   ⇒ n es O(n ² ) y n ² es O(n ³ ) entonces n es O(n ³ )
   Prueba:
   f(n) = O(g(n)) y g(n) = O(h(n)) ⇒ f(n) = O(h(n))
   Por la definición de Big-Oh(O) , existen constantes positivas c, no tales que f(n) ≤ cg(n) para todo n ≥ no
   ⇒ f(n) ≤ c1.g(n)
   ⇒ g(n) ≤ c2.h(n)
   ⇒ f (n) ≤ c1.c2h(n)
   ⇒ f(n) ≤ ch(n), donde, c = c1.c2 Por definición, f(n) = O(h(n))
   De manera similar,

   f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n))
   f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ⇒ f(n) = Ω(h(n))
   f(n) = o(g(n)) and g(n) = o(h(n)) ⇒ f(n) = o(h(n))
   f(n) = ω(g(n)) and g(n) = ω(h(n)) ⇒ f(n) = ω(h(n))

4. Transponer simetría:

   f(n) = O(g(n)) if and only if g(n) = Ω(f(n))

   Ejemplo:
   Si f(n) = n y g(n) = n ² entonces n es O(n ² ) y n ² es Ω(n)
   Prueba:

   • Parte necesaria:
     f(n) = O(g(n)) ⇒ g(n) = Ω(f(n))
     Por la definición de Big-Oh (O) ⇒ f(n) ≤ cg(n) para alguna constante positiva c ⇒ g(n) ≥ (1/c).f(n)
     Por la definición de Omega (Ω), g(n) = Ω(f(n))
   • Parte de suficiencia:
     g(n) = Ω(f(n)) ⇒ f(n) = O(g(n))
     Por la definición de Omega (Ω), para alguna constante positiva c ⇒ g(n) ≥ cf(n) ⇒ f(n) ≤ (1/c).g(n)
     Por la definición de Big-Oh(O), f(n) = O(g(n))

   Similarmente,

   f(n) = o(g(n)) if and only if g(n) = ω(f(n)) 

5. Dado que estas propiedades son válidas para las notaciones asintóticas, se pueden establecer analogías entre las funciones f(n) y g(n) y dos números reales a y b.
   • g(n) = O(f(n)) es similar a a ≤ b
   • g(n) = Ω(f(n)) es similar a a ≥ b
   • g(n) = Θ(f(n)) es similar a a = b
   • g(n) = o(f(n)) es similar a a < b
   • g(n) = ω(f(n)) es similar a a > b
6. Observaciones:

   max(f(n), g(n)) = Θ(f(n) + g(n)) 

   Prueba:
   Sin pérdida de generalidad, suponga que f(n) ≤ g(n), ⇒ max(f(n), g(n)) = g(n)
   Considere, g(n) ≤ max(f(n), g(n)) ≤ g(n)
   ⇒ g(n) ≤ max(f(n), g(n)) ≤ f(n) + g(n)
   ⇒ g(n)/2 + g(n) /2 ≤ max(f(n), g(n)) ≤ f(n) + g(n)
   De lo que asumimos, podemos escribir
   ⇒ f(n)/2 + g(n)/2 ≤ max( f(n), g(n)) ≤ f(n) + g(n)
   ⇒ (f(n) + g(n))/2 ≤ max(f(n), g(n)) ≤ f( n) + g(n)
   Por la definición de Θ, max(f(n), g(n)) = Θ(f(n) + g(n))

7. O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

   Prueba:
   Sin pérdida de generalidad, suponga f(n) ≤ g(n)
   ⇒ O(f(n)) + O(g(n)) = c1.f(n) + c2.g(n)
   De lo que asumido, podemos escribir
   O(f(n)) + O(g(n)) ≤ c1.g(n) + c2.g(n)
   ≤ (c1 + c2) g(n)
   ≤ cg(n)
   ≤ c.max(f(n), g(n))
   Por la definición de Big-Oh(O),
   O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

Nota:

1. Si lim _n→∞ f(n)/g(n) = c , c ∈ R+ entonces f(n) = Θ(g(n))
2. Si lim _n→∞ f(n)/g(n) ≤ c , c ∈ R (c puede ser 0) entonces f(n) = O(g(n))
3. Si lim _n→∞ f(n)/g(n) = 0 , entonces f(n) = O(g(n)) y g(n) = O(f(n))
4. Si lim _n→∞ f(n)/g(n) ≥ c , c ∈ R (c puede ser ∞) entonces f(n) = Ω(g(n))
5. Si lim _n→∞ f(n)/g(n) = ∞ , entonces f(n) = Ω(g(n)) y g(n) = Ω(f(n))