AALIE

Notaciones Asintóticas

Familias de funciones, cotas superiores, inferiores, exactas, estrictas y equivalencia asintótica.

4. Notaciones Asintóticas

Las notaciones asintóticas permiten resumir el comportamiento de un algoritmo con una sola expresión, ignorando constantes y términos pequeños. Se fijan en cómo crece la función cuando $n$ se va al infinito.

¿Por qué ignoramos los términos pequeños?

Porque para valores grandes de $n$ , el termino que más crece aplasta a todos los demás. Si $T (n) = n^{2} + 1000 n + 50000$ , cuando $n = 1000000$ , el termino $n^{2}$ vale $1 0^{12}$ mientras que $1000 n$ vale solo $1 0^{9}$ . Para el análisis asintótico el $n^{2}$ es lo —nico que importa.

¿Sobre qué trabajan?

Las notaciones trabajan sobre familias (conjuntos) de funciones. Decir $f \in O (g)$ es decir que $f$ pertenece al conjunto de todas las funciones que $g$ acota por arriba.

Las 6 notaciones del curso

$O$ (Big-O) — cota superior: $f$ no crece más r?pido que $g$
$Ω$ (Big-Omega) — cota inferior: $f$ no crece más lento que $g$
$Θ$ (Theta) — cota exacta: $f$ y $g$ crecen igual
$o$ (little-o) — cota superior estricta: $f$ crece estrictamente más lento que $g$
$ω$ (little-omega) — cota inferior estricta: $f$ crece estrictamente más r?pido que $g$
$\sim$ (Tilde / Cuchiflú) — equivalencia: $f$ y $g$ son asintóticamente idénticas

Clave

Antes de calcular cuálquier límite, identifica bien cuál función es $f$ (la que analizas) y cuál es $g$ (la de referencia). Eso determina que convención aplicar.

4.1 Big-O — Cota Superior: O(g(n))

¿Qué significa intuitivamente?

$O (g (n))$ establece un techo: a partir de cierto punto, $f (n)$ nunca supera a $g (n)$ multiplicada por alguna constante.

Definicion formal

Definicion de O(g(n))

$f (n) \in O (g (n))$ si existen una constante real $c > 0$ y un natural $n_{0}$ tales que:

\forall n \geq n_{0} : f (n) \leq c \cdot g (n)

Criterio con límites — las dos convenciones

Criterios de Big-O seg?n la convención usada

Convención	Limite	Criterio para f en O(g)	Razon
Convención A — $lim f (n) / g (n)$	$L = lim_{n \to \infty} \frac{f ( n )}{g ( n )}$	$L = 0$ o $L = c$ finita $(c > 0)$	Si L es finito, f no crece más r?pido que g.
Convención B — $lim g (n) / f (n)$ (curso)	$L = lim_{n \to \infty} \frac{g ( n )}{f ( n )}$	$L = c$ finita $(c > 0)$ o $L = \infty$	Si g/f tiende a infinito, g acota por arriba a f.

Nota

Si $f / g \to 0$ , entonces $g / f \to \infty$ . Es el mismo hecho matematico expresado al reves.

Ejemplo resuelto con ambas convenciones

f(n)=3n^2+5n pertenece a O(n^2)?

Convención A: f/g

Plantear

L = n \to \infty lim \frac{3 n ^{2} + 5 n}{n ^{2}}

Simplificar

L = n \to \infty lim (3 + \frac{5}{n})

Evaluar

L = 3

Conclusion

L = 3 \Rightarrow f \in O (n^{2})

Convención B: g/f (curso)

Plantear

L = n \to \infty lim \frac{n ^{2}}{3 n ^{2} + 5 n}

Simplificar

L = n \to \infty lim \frac{1}{3 + 5/ n}

Evaluar

L = \frac{1}{3}

Conclusion

L = \frac{1}{3} \Rightarrow f \in O (n^{2})

f(n)=3n^2+5n pertenece a O(n)?

Convención A: f/g

Plantear

L = n \to \infty lim \frac{3 n ^{2} + 5 n}{n}

Simplificar

L = n \to \infty lim (3 n + 5)

Evaluar

L = + \infty

Conclusion

L = \infty \Rightarrow f \in / O (n)

Convención B: g/f (curso)

Plantear

L = n \to \infty lim \frac{n}{3 n ^{2} + 5 n}

Simplificar

L = n \to \infty lim \frac{1}{3 n + 5}

Evaluar

L = 0

Conclusion

L = 0 \Rightarrow f \in / O (n)

Cuidado

Cuando el límite de Convención A da $\infty$ , el de Convención B da $0$ , y viceversa.

4.2 Omega — Cota Inferior: Ω(g(n))

¿Qué significa intuitivamente?

$Ω (g (n))$ establece un piso: a partir de cierto punto, $f (n)$ siempre está por encima de $g (n)$ multiplicada por alguna constante.

Definicion formal

Definicion de Omega(g(n))

$f (n) \in Ω (g (n))$ si existen una constante real $c > 0$ y un natural $n_{0}$ tales que:

\forall n \geq n_{0} : f (n) \geq c \cdot g (n)

Criterio con límites — las dos convenciones

Criterios de Omega seg?n la convención usada

Convención	Limite	Criterio para f en Omega(g)	Razon
Convención A — $lim f (n) / g (n)$	$L = lim_{n \to \infty} \frac{f ( n )}{g ( n )}$	$L = c$ finita $(c > 0)$ o $L = \infty$	Si f/g tiende a infinito, f crece mucho más que g.
Convención B — $lim g (n) / f (n)$ (curso)	$L = lim_{n \to \infty} \frac{g ( n )}{f ( n )}$	$L = 0$ o $L = c$ finita $(c > 0)$	Si g/f tiende a 0, g crece mucho más lento que f.

Ejemplo resuelto

f(n)=3n^2+5n pertenece a Omega(n)?

Convención A: f/g

Plantear

L = n \to \infty lim \frac{3 n ^{2} + 5 n}{n}

Simplificar

L = n \to \infty lim (3 n + 5)

Evaluar

L = + \infty

Conclusion

L = \infty \Rightarrow f \in Ω (n)

Convención B: g/f (curso)

Plantear

L = n \to \infty lim \frac{n}{3 n ^{2} + 5 n}

Simplificar

L = n \to \infty lim \frac{1}{3 n + 5}

Evaluar

L = 0

Conclusion

L = 0 \Rightarrow f \in Ω (n)

4.3 Theta — Cota Exacta: θ(g(n))

¿Qué significa intuitivamente?

$Θ (g (n))$ dice que $f$ y $g$ crecen exactamente al mismo ritmo asintótico.

Definicion de Theta(g(n))

\forall n \geq n_{0} : c_{1} g (n) \leq f (n) \leq c_{2} g (n)

Criterios de Theta seg?n la convención usada

Convención	Limite	Criterio para f en Theta(g)	Razon
Convención A	$lim f (n) / g (n)$	$L = c, 0 < c < \infty$	El cociente se estabiliza en una constante positiva.
Convención B (curso)	$lim g (n) / f (n)$	$L = c, 0 < c < \infty$	El reciproco de una constante positiva finita sigue siendo constante positiva finita.

Clave

Theta es el —nico caso donde el criterio numérico es igual en ambas convenciones: una constante positiva finita.

Convención A: f/g

Plantear

L = n \to \infty lim \frac{3 n ^{2} + 5 n}{n ^{2}}

Simplificar

L = n \to \infty lim (3 + \frac{5}{n})

Evaluar

L = 3

Convención B: g/f (curso)

Plantear

L = n \to \infty lim \frac{n ^{2}}{3 n ^{2} + 5 n}

Simplificar

L = n \to \infty lim \frac{1}{3 + 5/ n}

Evaluar

L = \frac{1}{3}

4.4 Little-o — Cota Superior Estricta: o(g(n))

Little-o es cómo Big-O pero más restrictivo: $f$ crece estrictamente más lento que $g$ .

Definicion de o(g(n))

\forall n \geq n_{0} : f (n) < c \cdot g (n)

Criterios de little-o seg?n la convención usada

Convención	Limite	Criterio	Razon
Convención A	$lim f (n) / g (n)$	$L = 0$	f/g tiende a cero.
Convención B (curso)	$lim g (n) / f (n)$	$L = + \infty$	g/f tiende a infinito.

Convención A: f/g

Plantear

L = n \to \infty lim \frac{n}{n ^{2}}

Simplificar

L = n \to \infty lim \frac{1}{n}

Evaluar

L = 0

Convención B: g/f (curso)

Plantear

L = n \to \infty lim \frac{n ^{2}}{n}

Evaluar

L = + \infty

Nota

$f \in o (g)$ implica $f \in O (g)$ , pero no al reves.

4.5 Little-omega — Cota Inferior Estricta: ω(g(n))

Little-omega es el espejo de little-o: $f$ crece estrictamente más r?pido que $g$ .

Definicion de omega(g(n))

\forall n \geq n_{0} : f (n) > c \cdot g (n)

Criterios de little-omega seg?n la convención usada

Convención	Limite	Criterio	Razon
Convención A	$lim f (n) / g (n)$	$L = + \infty$	f/g tiende a infinito.
Convención B (curso)	$lim g (n) / f (n)$	$L = 0$	g/f tiende a cero.

Convención A: f/g

Plantear

L = n \to \infty lim \frac{n ^{2}}{n}

Evaluar

L = + \infty

Convención B: g/f (curso)

Plantear

L = n \to \infty lim \frac{n}{n ^{2}}

Evaluar

L = 0

4.6 Tilde (~) — Equivalencia Asintótica

La tilde es la notación más exigente: exige que el cociente entre las funciones tienda exactamente a 1.

Comparacion con Theta

Si Theta es crecen igual hasta constante multiplicativa, la tilde es crecen exactamente igual y esa constante es 1.

Definicion de ~ (Tilde)

f (n) \sim g (n) ⟺ n \to \infty lim \frac{f ( n )}{g ( n )} = 1

Criterios de tilde seg?n la convención usada

Convención	Limite	Criterio para f ~ g	Razon
Convención A	$lim f (n) / g (n)$	$L = 1$	Las funciones son asintóticamente idénticas.
Convención B (curso)	$lim g (n) / f (n)$	$L = 1$	Si f~g, entonces g/f tambien tiende a 1.

Clave

La tilde exige L=1. Theta, en cambio, acepta cuálquier constante positiva finita.

Convención A: f/g

Plantear

L = n \to \infty lim \frac{n ^{2} + n}{n ^{2}}

Simplificar

L = n \to \infty lim (1 + \frac{1}{n})

Evaluar

L = 1

Convención B: g/f (curso)

Plantear

L = n \to \infty lim \frac{n ^{2}}{n ^{2} + n}

Simplificar

L = n \to \infty lim \frac{1}{1 + 1/ n}

Evaluar

L = 1

Nota

La tilde implica Theta, pero Theta no implica tilde. Por ejemplo, $3 n^{2}$ tiene $Θ (n^{2})$ pero no es $\sim n^{2}$ .