Notación asintótica (O, o, Ω, Θ)

Los símbolos de Landau comparan funciones salvo factores constantes: $f = O(g)$ (no crece más deprisa), $f = \Omega(g)$ (no más despacio), $f = \Theta(g)$ (al mismo ritmo), $f = o(g)$ (estrictamente más despacio). Nacieron en teoría de números, la informática los adoptó para clasificar algoritmos y el análisis numérico para medir errores.

Los tiempos exactos dependen de la máquina, el compilador y la entrada. Lo que sobrevive a cualquier cambio de hardware es la forma del crecimiento: duplicar la entrada cuadruplica el tiempo de un algoritmo $O(n^2)$ en cualquier ordenador. La notación asintótica captura justo eso y tira el resto.

$f = O(g)$: a partir de cierto punto, la gráfica de $f$ se queda por debajo de una copia estirada $C\,g$. O es una cota superior, Ω una cota inferior y Θ un sándwich. La o pequeña dice que el cociente $f/g$ tiende a cero: en análisis numérico, $e(h) = o(h)$ significa «el error se anula más deprisa que el paso».

Cuando $n \to \infty$ (o $x \to a$):

• $f = O(g) \iff \exists C, n_0:\ |f(n)| \le C\,|g(n)|$ para $n \ge n_0$
• $f = \Omega(g) \iff g = O(f)$
• $f = \Theta(g) \iff f = O(g)$ y $f = \Omega(g)$
• $f = o(g) \iff \lim f(n)/g(n) = 0$

¿Es $n \log n = O(n^{1{,}1})$? Sí: $\frac{n\log n}{n^{1{,}1}} = \frac{\log n}{n^{0{,}1}} \to 0$, así que incluso es $o(n^{1{,}1})$. Pero el punto de cruce es enorme: $\log n = n^{0{,}1}$ hacia $n \approx 10^{15}$. La asintótica dice quién gana al final, no cuándo.

Es el vocabulario del diseño de algoritmos («esto es $O(n \log n)$»), de los métodos numéricos («Runge–Kutta 4 tiene error $O(h^4)$»), de Monte Carlo («error $O(N^{-1/2})$») y de la teoría del aprendizaje (cotas de generalización). Una notación, tres comunidades.