## 1.2.2 NOTACIÓN O MAYÚSCULA

La notación O se utiliza para comparar funciones. Resulta particularmente útil cuando se quiere analizar la complejidad de un algoritmo, en otras
palabras, la cantidad de tiempo que le toma a un computador ejecutar un programa.

Definición: Sean f y g funciones con dominio en R ≤ 0 o N es imagen en R. Si existen constantes C y k tales que:
∀ x > k, | f (x) | ≤ C | g (x) |
es decir, que para x > k, f es menor o igual a un multiplo de g, decimos que:
f (x) = O ( g (x) )

La definición formal es:
f (x) = O ( g (x) ) ∃ k , N | ∀ x > N, | f (x) | ≤ k| g (x) |

¿Qué quiere decir todo esto? Básicamente, que una función es siempre menor que otra función (por ejemplo, el tiempo en ejecutar un programa es menor que x2) si no tenemos en cuenta los factores constantes (eso es lo que significa la k) y si no tenemos en cuenta los valores pequeños (eso es lo que significa la N).

¿Por qué no tenemos en cuenta los valores pequeños de N? Porqué para entradas pequeñas, el tiempo que tarda el programa no es significativo y
casi siempre el algoritmo será suficientemente rápido para lo que queremos.

Así 3N3 + 5N2– 9 = O (N3) no significa que existe una función O(N3) que es igual a 3N3 + 5N2– 9. Debe leerse como:"3N3+5N2–9 es O-Grande de N3" que significa:"3N3+5N2–9 está asintóticamente dominada por N3"

Veamos algunos ejemplos.

Ejemplo 1: Muestre que 3N3 + 5N2 – 9 = O (N3).
De nuestra experiencia anterior pareciera tener sentido que C = 5.
Encontremos k tal que:
3N3 + 5N2 – 9 ≤ 5N3 for N > k :
1. Agrupamos: 5N2 ≤ 2N3 + 9
2. Cuál k asegura que 5N2≤ N3 para N > k?
3. k = 5
4. Así que para N > 5, 5N2 ≤ N3 ≤ 2N3 + 9.
5. C = 5, k = 5

Ejemplo 2: Muestre que N 4 ≠ O (3N3 + 5N2 – 9) .
Hay que mostrar que no existen C y k tales que para N > k, C* (3N3 + 5N2 – 9) ≥ N4 es siempre cierto (usamos límites).
lim x4 / C(3x3 + 5 x2– 9) = lim x / C(3 + 5/x – 9/x3)
x -> ∞ x -> ∞

= lim x / C(3 + 0 – 0) = (1/3C) . lim x = ∞

x -> ∞ x -> ∞

Así que sin importar cual sea el C que se elija, N4 siempre alcanzará y rebasará C* (3N3 + 5N2 – 9).

Lema: Si el límite cuando x -> ∞ del cociente |f (x)/g (x)| existe (es finito)
entonces f (x) = O ( g (x) ).

Ejemplo 3: 3N3 + 5N2 – 9 = O (N3 ). Calculamos:
lim x3 / (3x3 + 5x2 – 9) = lim 1 /(3 + 5/x – 9/x3) = 1 /3
x -> ∞ x -> ∞

###