2026-08-25 ADA - notacion_asintotica

Pregunta central

¿Cómo comparamos algoritmos sin depender de una computadora concreta y cómo expresamos rigurosamente la rapidez con la que crece su costo?

Respuesta corta

Se define el tamaño $n$ de la entrada, se fija un modelo de cómputo y se cuentan operaciones primitivas para obtener $T(n)$. Luego se conserva el orden de crecimiento con $O$ (cota superior), $\Omega$ (cota inferior) o $\Theta$ (cota ajustada). Esta abstracción permite comparar escalamiento, aunque para entradas concretas también importan constantes, memoria y hardware.

Mapa de la clase

flowchart TB
  P["Problema"] --> N["Tamaño n"]
  N --> M["Modelo de cómputo"]
  M --> C["Contar: T(n)"]
  C --> A["Simplificar crecimiento"]
  A --> O["O: techo"]
  A --> OM["Ω: piso"]
  A --> TH["Θ: cota ajustada"]
  TH --> E["Comparar escalamiento"]

Del problema a una cota asintótica

El análisis no empieza adivinando una letra $O$. Se avanza en orden: definir qué crece, decidir qué operaciones cuestan una unidad, especificar qué caso se estudia, contar y solo entonces simplificar.

---

1. ¿Qué significa analizar un algoritmo?

Charles Babbage ya formulaba la pregunta esencial: si una máquina puede obtener el mismo resultado de varias maneras, ¿qué secuencia lo obtiene con menos trabajo? En su máquina analítica la intuición era cuántas veces hay que girar la manivela.

Hoy se miden principalmente dos recursos:

• Tiempo: número de operaciones primitivas ejecutadas.
• Memoria: número de celdas ocupadas.

El conteo solo tiene sentido después de declarar el modelo de cómputo.

Paso 1: definir el tamaño de la entrada

El símbolo $n$ debe medir la cantidad de información recibida:

• arreglo: $n$ = número de elementos;
• cadena: $n$ = número de símbolos;
• grafo: suelen intervenir $n=|V|$ vértices y $m=|E|$ aristas;
• entero $x$: el tamaño es aproximadamente ${\log }_{2}x$ bits, no el valor $x$.

Por qué importa

Un algoritmo que realiza $x$ pasos no es lineal en el tamaño binario del entero: como $x\approx 2^n$, puede ser exponencial en $n$.

Paso 2: fijar el modelo de cómputo

Modelo	Qué cuenta como paso	Ventaja	Limitación
Máquina de Turing determinista	Transición, lectura/escritura y movimiento del cabezal	Modelo teórico simple	No ofrece acceso aleatorio
Word RAM	Aritmética/lógica, acceso a arreglo, lectura/escritura, apuntadores y saltos	Se parece a una computadora real	Operaciones con enteros enormes requieren un modelo más fino

En word RAM, cada palabra tiene $w$ bits y se supone $w\ge {\log }_{2}n$, para que un índice o dirección quepa en una palabra.

flowchart LR
  IN["entrada"] --> CPU["programa"]
  CPU <-->|"leer/escribir en Θ(1)"| MEM["memoria word RAM"]
  MEM --> ARR["A[i]"]
  MEM --> PTR["seguir apuntador"]
  CPU --> OUT["salida"]

El modelo puede cambiar la respuesta

Reconocer un palíndromo de $n$ bits requiere al menos orden cuadrático en una máquina de Turing de una cinta, mientras que con acceso aleatorio puede hacerse en tiempo lineal. No hay contradicción: cambiaron las operaciones permitidas.

Paso 3: elegir el tipo de análisis

Tipo	Pregunta que responde	Ejemplo
Peor caso	¿Cuál es el máximo costo entre entradas de tamaño $n$?	Garantía para cualquier entrada
Esperado (probabilístico)	¿Cuál es el costo esperado del azar del algoritmo?	Quicksort aleatorio usa cerca de $2n\ln n$ comparaciones en esperanza
Amortizado	¿Cuánto cuesta cualquier secuencia completa de operaciones?	$n$ push/pop en un arreglo redimensionable cuestan $O(n)$ en total
Caso promedio	¿Cuál es el promedio bajo una distribución de entradas?	Requiere justificar esa distribución

El peor caso se formaliza como

$$T_{\max }(n)=\underset{|x|=n}{\max }T(x).$$

No debe confundirse tiempo esperado con caso promedio: el primero promedia el azar interno del algoritmo para una entrada fija; el segundo promedia entradas según una distribución.

Excepciones prácticas

En la vida cotidiana, se usan algoritmos de tiempo exponencial ya que los peores casos no aparecen (simplex, grep linux, k-means).

---

2. Tratabilidad computacional

Fuerza bruta

Un algoritmo de fuerza bruta enumera soluciones candidatas y verifica cada una. Suele ser fácil de describir, pero puede necesitar $2^n$, $n!$ o más pasos.

En emparejamiento estable, probar los $n!$ emparejamientos perfectos y verificar su estabilidad es correcto, pero impracticable incluso para valores moderados de $n$.

Tiempo polinomial

Un algoritmo es de tiempo polinomial si existen constantes $a>0$ y $b>0$ tales que, para toda entrada de tamaño $n$,

$$T(n)\le a{n}^b.$$

La propiedad clave aparece al duplicar la entrada:

$$T(2n)\le a(2n{)}^b=2^{b}a{n}^b.$$

El costo aumenta por un factor constante $2^b$, independiente de $n$.

flowchart TB
  N["entrada n"] --> D["entrada 2n"]
  D --> P["nᵇ: multiplica por 2ᵇ"]
  D --> E["2ⁿ: pasa de 2ⁿ a 2²ⁿ"]
  P --> T["escalamiento controlado"]
  E --> X["explosión combinatoria"]

En teoría se llama eficiente a un algoritmo polinomial porque esta clase es relativamente estable ante cambios razonables del modelo de cómputo. En la práctica, la palabra eficiente exige más cuidado.

Polinomial no significa automáticamente práctico

$20n^{120}$ es polinomial, pero sus constantes y exponente lo hacen inútil para casi cualquier entrada. El análisis asintótico describe el comportamiento cuando $n$ crece; no reemplaza una evaluación concreta.

Eficiencia aslgorítimca

Decimos que un algoritmo es eficiente si tiene tiempo de ejecucion polinomial.

3. Notación asintótica

Sea $f(n)$ el costo y $g(n)$ una función de referencia. Las notaciones ignoran constantes multiplicativas y una cantidad finita de valores iniciales, pero responden preguntas distintas.

$O(g(n))$: cota superior

$$f(n)\in O(g(n))⟺\exists c>0,\exists n_0\ge 0:0\le f(n)\le cg(n)\forall n\ge n_0.$$

Interpretación: desde cierto punto, $cg(n)$ es un techo para $f(n)$.

$\Omega (g(n))$: cota inferior

$$f(n)\in \Omega (g(n))⟺\exists c>0,\exists n_0\ge 0:f(n)\ge cg(n)\ge 0\forall n\ge n_0.$$

Interpretación: desde cierto punto, $cg(n)$ es un piso para $f(n)$.

Además,

$$f(n)\in \Omega (g(n))⟺g(n)\in O(f(n)).$$

$\Theta (g(n))$: cota ajustada

$$f(n)\in \Theta (g(n))⟺\exists c_1,c_2>0,\exists n_0\ge 0:0\le c_{1}g(n)\le f(n)\le c_{2}g(n)$$

para todo $n\ge n_0$. Por tanto,

$$f\in \Theta (g)⟺f\in O(g)\wedge f\in \Omega (g).$$

Mnemotecnia

$O$ es techo, $\Omega$ es piso y $\Theta$ es el sándwich entre ambos.

Visualización de las tres cotas

En el ejemplo $f(n)=32n^2+17n+1$, la curva queda por debajo de $50n^2$ y por encima de $32n^2$ para $n\ge 1$. Cambia de vista para observar el techo, el piso y su combinación.

Ejemplo completo con constantes explícitas

Sea

$$f(n)=32n^2+17n+1.$$

Para $n\ge 1$, se cumple $n\le n^2$ y $1\le n^2$, así que

$$f(n)\le 32n^2+17n^2+n^2=50n^2.$$

Esto prueba $f\in O(n^2)$ con $c_2=50$ y $n_0=1$. También,

$$f(n)\ge 32n^2,$$

por lo que $f\in \Omega (n^2)$ con $c_1=32$. Juntando ambos resultados,

$$32n^2\le f(n)\le 50n^2(n\ge 1),$$

y entonces

$$\boxed{f(n)\in \Theta (n^2)}.$$

Una cota correcta puede ser poco informativa

Para

$$f(n)=3n^2+17n{\log }_{2}n+1000,$$

son ciertas las afirmaciones $f\in O(n^2)$ y $f\in O(n^3)$. La segunda es más floja: no es falsa, solo describe peor el crecimiento real.

Abuso de notación

$O(g(n))$ es un conjunto de funciones. Lo formal es escribir

$$f(n)\in O(g(n)).$$

Es común ver $f(n)=O(g(n))$, pero esa “igualdad” solo expresa pertenencia. De $5n^3=O(n^3)$ y $3n^2=O(n^3)$ no se deduce que $5n^3=3n^2$.

Algoritmo frente a problema

“Este algoritmo usa $O(n\log n)$ comparaciones” acota una estrategia. “Todo algoritmo de ordenamiento por comparaciones necesita $\Omega (n\log n)$” acota el problema dentro de un modelo.

---

4. Reglas para simplificar costos

Propiedades de $O$

1. Reflexividad: $f\in O(f)$.
2. Constantes: si $f\in O(g)$ y $c>0$, entonces $cf\in O(g)$.
3. Productos: si $f_1\in O(g_1)$ y $f_2\in O(g_2)$, entonces $f_1{f}_2\in O(g_1{g}_2)$.
4. Sumas: $f_1+f_2\in O(\max \{g_1,g_2\})$.
5. Transitividad: si $f\in O(g)$ y $g\in O(h)$, entonces $f\in O(h)$.

La regla de sumas justifica ignorar términos menores:

$$5n^3+3n^2+n+1234\in \Theta (n^3).$$

Por qué funciona la regla del producto

Si, para $n$ suficientemente grande,

$$0\le f_1(n)\le c_1{g}_1(n),0\le f_2(n)\le c_2{g}_2(n),$$

entonces, al multiplicar,

$$0\le f_1(n)f_2(n)\le c_1{c}_2{g}_1(n)g_2(n).$$

La desigualdad vale desde $n_0=\max \{n_1,n_2\}$.

Criterio del cociente

Cuando existe

$$L=\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)},$$

se obtiene:

Valor de $L$	Conclusión
$0<L<\infty$	$f\in \Theta (g)$
$L=0$	$f\in O(g)$ y $f\notin \Omega (g)$
$L=\infty$	$f\in \Omega (g)$ y $f\notin O(g)$

El recíproco de la primera fila es falso: $f\in \Theta (g)$ no obliga a que $f/g$ tenga límite; el cociente puede oscilar entre dos constantes positivas.

Familias comunes

• Si $f(n)=a_0+a_{1}n+\cdots +a_d{n}^d$ con $a_d>0$, entonces $f\in \Theta (n^d)$.
• Las bases constantes de los logaritmos difieren solo por una constante:

$${\log }_{a}n=\frac{{\log }_{b}n}{{\log }_{b}a}\in \Theta ({\log }_{b}n).$$

• Para $a>1$ y $d>0$, ${\log }_{a}n\in O(n^d)$.
• Para $r>1$ y $d>0$, $n^d\in O(r^n)$.
• Por la fórmula de Stirling, $n!=2^{\Theta (n\log n)}$.

flowchart LR
  C["1"] --> LG["log n"] --> N["n"] --> NL["n log n"] --> N2["n²"] --> N3["n³"] --> EX["2ⁿ"] --> FAC["n!"]

Cada flecha significa “crece asintóticamente más lento que”.

Funciones de varias variables

Si

$$f(m,n)=32m{n}^2+17mn+32n^3,$$

entonces

$$f(m,n)\in O(m{n}^2+n^3).$$

Solo con una precondición como $m\le n$ puede simplificarse a $O(n^3)$. Por la misma razón, el costo $O(m+n)$ de BFS no debe reducirse a $O(n)$ sin una relación entre aristas y vértices.

---

Método de examen

1. Escribir qué significa $n$.
2. Identificar el modelo y las operaciones de costo constante.
3. Indicar si se analiza peor caso, esperanza o costo amortizado.
4. Obtener una expresión $T(n)$ antes de simplificar.
5. Para demostrar $O$, proponer $c$ y $n_0$ y verificar un techo.
6. Para demostrar $\Omega$, proponer $c$ y $n_0$ y verificar un piso.
7. Para concluir $\Theta$, demostrar ambos con la misma función de referencia.

Errores frecuentes

• Confundir $O$ con “igualdad exacta” o con “peor caso”.
• Decir que $O(n^3)$ es falso para una función $\Theta (n^2)$: es cierto, pero flojo.
• Escribir “requiere al menos $O(n\log n)$”; una cota inferior se expresa con $\Omega$.
• Eliminar $m$ de un costo $O(m+n)$ sin una precondición.
• Usar una gráfica con pocos valores como demostración: la desigualdad debe valer para todo $n\ge n_0$.
• Creer que polinomial significa siempre rápido en la práctica.

Quizzes de las diapositivas 13, 17–20

Quiz	Respuesta	Razón
1	C	$f\in O(n^2)$ y por transitividad también $f\in O(n^3)$
2	A	$f\in \Omega (g)⟺g\in O(f)$; cumplir la desigualdad para infinitos $n$ no basta
3	A	$O(g)\cap \Omega (g)=\Theta (g)$; el cociente puede oscilar y no tener límite

Autoevaluación

• Puedo explicar por qué el tamaño de un entero es su número de bits.
• Puedo distinguir word RAM de una máquina de Turing de una cinta.
• Puedo diferenciar peor caso, esperado, amortizado y caso promedio.
• Puedo demostrar $32n^2+17n+1\in \Theta (n^2)$ con constantes explícitas.
• Puedo explicar por qué una cota superior no tiene que ser ajustada.
• Puedo analizar una función que dependa de $m$ y $n$ sin ocultar variables.

Resumen después de clase

Analizar un algoritmo consiste en convertir su ejecución en una función de costo bien definida. El modelo word RAM aproxima operaciones comunes de una computadora y el peor caso ofrece una garantía para toda entrada. El tiempo polinomial captura un escalamiento controlado. Finalmente, $O$, $\Omega$ y $\Theta$ permiten hablar de techos, pisos y cotas ajustadas ignorando constantes y comportamiento inicial, pero sin olvidar las hipótesis ni las variables de la entrada.

Conexión con la siguiente clase

La diapositiva 24 abre la sección de implementación. El jueves se usará todo lo anterior para demostrar que una representación cuidadosa de Gale–Shapley alcanza $\Theta (n^2)$ y para estudiar ejemplos de $O(1)$ a tiempo exponencial.

→ Jueves 27 — Implementación y tiempos de ejecución

Referencias

• Kevin Wayne, Algorithm Analysis, diapositivas 1–24, actualización del 16 de diciembre de 2021.
• Jon Kleinberg y Éva Tardos, Algorithm Design, capítulo 2.