> ## Documentation Index > Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt > Use this file to discover all available pages before exploring further. # Notación asintótica O, Ω y θ y relaciones de recurrencia > Notación asintótica explicada: O grande, omega y theta, jerarquía de órdenes, comparar costes con límites y resolver recurrencias de sustracción y división, con ejemplos resueltos. Compara dos costes con el límite del cociente, busca c y n₀ y resuelve recurrencias con su árbol de llamadas. Un algoritmo tarda $3n^2 + 4n + 4$ pasos y otro $4n + 4$. ¿Cuál es mejor? Para tallas pequeñas la respuesta depende de los detalles, pero a partir de cierto tamaño siempre gana el segundo, porque **crece más despacio**. La notación asintótica sirve para decir eso con precisión: olvida las constantes y las tallas pequeñas y se queda con lo que decide en problemas grandes, **cómo crece el coste**. Es el idioma con el que se comparan algoritmos. ## Lo que vas a aprender * Qué significan $O$, $\Omega$ y $\theta$, y cómo se demuestra que una función está en una de ellas. * La jerarquía de órdenes, de $O(1)$ a $O(n^n)$. * Comparar dos costes con el límite de su cociente. * Las reglas de la suma y del producto, y las sumas que aparecen al contar pasos. * Plantear la recurrencia de un algoritmo recursivo y resolverla por sustitución. * Comprobar el resultado con los modelos generales de sustracción y división. ## Cómo se usa el simulador **Pestaña «Comparar órdenes»** | Control | Qué hace | | - | - | | **f(n)** y **g(n)** | Los dos costes, escritos en función de $n$: `3n^3`, `n log(n)`, `2^n`, `sqrt(n)`… | | **Ejemplos** | Parejas típicas: $3n^3$ frente a $600n^2$, la base del logaritmo, $2^n$ frente a $n^3$… | | **Escala** | Eje vertical lineal o logarítmico, para ver juntas funciones muy distintas | | **n · hasta** | Hasta qué talla se dibuja (de 10 a un millón) | El panel de la derecha da el **límite del cociente** $f/g$ y la conclusión, los valores de $c$ y $n_0$ que cumplen la definición de $O$ y de $\Omega$ (con $c \cdot g(n)$ dibujada a trazos) y la talla en la que las dos curvas se cruzan. **Pestaña «Recurrencias»** | Control | Qué hace | | - | - | | **Modelo** | Sustracción, $T(n - b)$, o división, $T(n / b)$ | | **a** | Número de llamadas recursivas | | **b** | Cuánto se resta o entre cuánto se divide la talla | | **k** | Exponente del trabajo no recursivo, $c\,n^k$ | | **Ejemplos** | Factorial, selección, búsqueda binaria, mergesort, Karatsuba… | Se muestran la recurrencia, su expansión tras $i$ pasos, el **coste de cada nivel del árbol de llamadas**, la solución según la tabla y una comprobación numérica: $T(n)$ calculado con la recurrencia y dividido entre el orden de la solución, que debe tender a una constante. El logaritmo se escribe `log` y es el neperiano. La base no cambia el orden; si quieres $\log_2 n$ exacto, escribe `log(n)/log(2)`. ## Fundamentos teóricos ### Talla, paso y principio de invarianza La **talla** es lo que mide el tamaño del problema: el número de elementos de un vector, las dimensiones de una matriz, el propio número. Un **paso** es un fragmento de código que tarda un tiempo acotado por una constante, sin importar la talla: una suma, una comparación, una asignación. El coste se mide en pasos, no en segundos. Según el **principio de invarianza**, dos implementaciones del mismo algoritmo solo se diferencian en una constante multiplicativa. Un ordenador diez veces más rápido divide el tiempo entre diez, pero no cambia la forma en que crece. Por eso las constantes se ignoran y se estudia el **orden**. ### Las tres notaciones Sean $f, g: \mathbb{N} \to \mathbb{R}^+$, con $f(n)$ el coste del algoritmo. **Cota superior, $O$:** $g$ domina a $f$ a partir de un punto. $$ f(n) \in O(g(n)) \iff \exists\, c \in \mathbb{R}^+,\ \exists\, n_0 \in \mathbb{N} : \quad f(n) \le c\, g(n) \quad \forall n \ge n_0 $$ **Cota inferior, $\Omega$:** hay un múltiplo de $g$ que $f$ nunca baja. $$ f(n) \in \Omega(g(n)) \iff \exists\, c \in \mathbb{R}^+,\ \exists\, n_0 \in \mathbb{N} : \quad f(n) \ge c\, g(n) \quad \forall n \ge n_0 $$ **Orden exacto, $\theta$:** las dos a la vez. $$ f(n) \in \theta(g(n)) \iff \exists\, c_1, c_2, n_0 : \ c_1\, g(n) \le f(n) \le c_2\, g(n) \ \ \forall n \ge n_0 $$ Para demostrar que $f \in O(g)$ basta con dar una pareja $c$, $n_0$ que funcione. Por ejemplo, $3n + 2 \in O(n)$ porque con $c = 4$ se cumple $3n + 2 \le 4n$ para todo $n \ge 2$. Es justo lo que calcula el simulador. ### Jerarquía de órdenes $$ O(1) \subset O(\log n) \subset O(\sqrt{n}) \subset O(n) \subset O(n \log n) $$ $$ \subset O(n^2) \subset O(n^3) \subset O(2^n) \subset O(n^n) $$ | Tipo | Orden | Ejemplo | | - | - | - | | Constante | $O(1)$ | Acceder a un elemento de un vector | | Logarítmica | $O(\log n)$ | Búsqueda binaria | | Lineal | $O(n)$ | Búsqueda secuencial | | Superlineal | $O(n \log n)$ | Mergesort | | Cuadrática | $O(n^2)$ | Ordenación por selección | | Cúbica | $O(n^3)$ | Producto de matrices clásico | | Exponencial | $O(2^n)$ | Probar todos los subconjuntos | Como $O(n) \subset O(n^2)$, la función $3n + 2$ está en $O(n)$, pero también en $O(n^2)$ y en $O(2^n)$. Siempre se da **la cota más ajustada**. Con $\Omega$ las inclusiones van al revés. ### Comparar órdenes con límites La forma más rápida de comparar dos funciones es el límite de su cociente: | $\displaystyle\lim_{n\to\infty} \frac{f(n)}{g(n)}$ | Conclusión | | - | - | | $k$, con $0 \lt k \lt \infty$ | $f \in \theta(g)$: el mismo orden | | $\infty$ | $f$ crece más deprisa: $f \in \Omega(g)$ y $f \notin O(g)$ | | $0$ | $g$ crece más deprisa: $f \in O(g)$ y $f \notin \Omega(g)$ | Con este criterio se ve que **la base del logaritmo no importa**: para $a, b > 1$, $$ \lim_{n\to\infty} \frac{\log_a n}{\log_b n} = \log_a b \ne 0 \quad\Longrightarrow\quad \theta(\log_a n) = \theta(\log_b n) $$ ### Propiedades Todas valen igual con $O$, con $\Omega$ y con $\theta$. * **Polinomios:** un polinomio de grado $k$ es $\theta(n^k)$. Se queda el término de mayor grado. * **Regla de la suma:** $\theta(f) + \theta(g) = \theta(\max(f, g))$. Dos bucles seguidos cuestan lo que el más caro. * **Regla del producto:** $\theta(f) \cdot \theta(g) = \theta(f \cdot g)$. Un bucle dentro de otro multiplica. * **Constantes:** si $f \in \theta(h)$, también $a f + b \in \theta(h)$ para $a > 0$. ### Sumas habituales Al contar los pasos de bucles anidados aparecen siempre las mismas sumas: $$ \sum_{i=1}^{n} 1 = n \qquad \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \qquad \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} $$ | Suma | Orden | | - | - | | $\sum_{i=1}^{n} i^k$ | $\theta(n^{k+1})$ | | $\sum_{i=1}^{n} r^i$, con $r > 1$ | $\theta(r^n)$ | | $\sum_{i=1}^{n} 1/i$ | $\theta(\log n)$ | | $\sum_{i=1}^{n} 1/r^i$, con $r > 1$ | $\theta(1)$ | ### Mejor y peor caso Si con la talla fija el coste cambia según los datos (las **instancias**), se estudian el mejor y el peor caso. Entonces el coste se da con $\Omega$ para el mejor caso y con $O$ para el peor. La búsqueda secuencial es $\Omega(1)$ (el elemento está el primero) y $O(n)$ (no está). Si no hay instancias, se da directamente con $\theta$. ### Algoritmos recursivos: relaciones de recurrencia El coste de un algoritmo recursivo se escribe en función de sí mismo: $$ T(n) = \begin{cases} c_1 & \text{en el caso base} \\ a\,T(s(n)) + p(n) & \text{en otro caso} \end{cases} $$ donde $a$ es el número de llamadas, $s(n)$ la talla de cada una (normalmente $n - b$ o $n/b$) y $p(n)$ el trabajo que no es recursivo. Se resuelve por **sustitución**: se cambia $T(\cdot)$ por su definición una y otra vez hasta ver el término general, y se llega al caso base. ### Modelos generales de recurrencia **Sustracción** (la talla se reduce restando $b$): $$ T(n) = a\,T(n - b) + c\,n^k \quad\Longrightarrow\quad T(n) \in \begin{cases} \theta(n^k) & a \lt 1 \\ \theta(n^{k+1}) & a = 1 \\ \theta(a^{\,n \operatorname{div} b}) & a \gt 1 \end{cases} $$ **División** (la talla se divide entre $b$): $$ T(n) = a\,T(n / b) + c\,n^k \quad\Longrightarrow\quad T(n) \in \begin{cases} \theta(n^k) & a \lt b^k \\ \theta(n^k \log n) & a = b^k \\ \theta(n^{\log_b a}) & a \gt b^k \end{cases} $$ En los exámenes de Algoritmia la tabla no se puede usar, salvo que se diga lo contrario: la complejidad se obtiene resolviendo la recurrencia. La tabla sirve para comprobar el resultado. ### Por qué salen esos tres casos: el árbol de llamadas En el modelo de división, el nivel $j$ del árbol tiene $a^j$ llamadas de talla $n/b^j$, y cada una hace $c\,(n/b^j)^k$ pasos. El nivel entero cuesta: $$ a^j \cdot c\left(\frac{n}{b^j}\right)^k = c\,n^k \left(\frac{a}{b^k}\right)^j $$ Es una progresión geométrica de razón $a/b^k$, con $\log_b n$ niveles: * Si $a \lt b^k$, cada nivel cuesta menos que el anterior y **manda la raíz**: $\theta(n^k)$. * Si $a = b^k$, **todos los niveles cuestan lo mismo**, $c\,n^k$, y hay $\log_b n$: $\theta(n^k \log n)$. * Si $a \gt b^k$, cada nivel cuesta más y **mandan las hojas**, que son $a^{\log_b n} = n^{\log_b a}$. El simulador dibuja una barra por nivel con su coste: se ve de un vistazo cuál de los tres casos es. ## Ejemplos resueltos Demuestra que $10n^2 + 4n + 2 \in \theta(n^2)$. **Cota inferior:** $10n^2 + 4n + 2 \ge 10n^2$ para todo $n \ge 0$, así que vale $c_1 = 10$. **Cota superior:** para $n \ge 1$, $4n \le 4n^2$ y $2 \le 2n^2$, luego $10n^2 + 4n + 2 \le 16n^2$. Vale $c_2 = 16$ con $n_0 = 1$. Con el límite es inmediato: $\lim \dfrac{10n^2 + 4n + 2}{n^2} = 10$, una constante distinta de cero. El simulador encuentra $c = 11$ con $n_0 = 5$: también vale, porque no hay una única pareja. Asintóticamente es mejor $600n^2$, porque $\lim \dfrac{3n^3}{600n^2} = \lim \dfrac{n}{200} = \infty$. Pero $3n^3 \ge 600n^2 \iff n \ge 200$. Para tallas menores que 200, el algoritmo cúbico da **menos** pasos. Si casi todos los problemas reales son pequeños, conviene el cúbico; para cualquier talla, se pueden combinar los dos y llamar a uno u otro según $n$. ``` Función Factorial(n: entero) retorna (entero) si (n = 0) entonces retorna 1 sino retorna n * Factorial(n-1) ``` $T(n) = \begin{cases} c_1 & n = 0 \\ T(n-1) + c_2 & n \gt 0 \end{cases}$ Expandiendo: $T(n) = T(n-1) + c_2 = T(n-2) + 2c_2 = \dots = T(n-i) + i\,c_2$. Se llega al caso base cuando $i = n$: $T(n) = c_1 + n\,c_2 \in \theta(n)$ **Comprobación:** sustracción con $a = 1$, $b = 1$, $k = 0$: $\theta(n^{k+1}) = \theta(n)$. ✓ Divide el vector en dos mitades, ordena cada una y las mezcla en tiempo lineal: $T(n) = 2\,T(n/2) + c\,n$ Expandiendo: $T(n) = 2^i\,T(n/2^i) + i\,c\,n$. El caso base se alcanza con $n/2^i = 1$, es decir, $i = \log_2 n$: $T(n) = n\,T(1) + c\,n\log_2 n \in \theta(n \log n)$ **Comprobación:** división con $a = 2$, $b = 2$, $k = 1$; como $a = b^k = 2$, sale $\theta(n \log n)$. ✓ En el árbol, los $\log_2 n$ niveles cuestan $c\,n$ cada uno. ``` Función Ejemplo(n) retorna (entero) si n = 1 entonces retorna 1 sino retorna n * Ejemplo(n-1) * Ejemplo(n div 2) ``` $T(n) = T(n-1) + T(n \operatorname{div} 2) + c$ no se resuelve directamente. Se acota por los dos lados: * **Por debajo**, cambiando $T(n-1)$ por el más pequeño $T(n \operatorname{div} 2)$: $T_1(n) = 2T_1(n/2) + c \in \theta(n)$. * **Por arriba**, cambiando $T(n \operatorname{div} 2)$ por el más grande $T(n-1)$: $T_2(n) = 2T_2(n-1) + c \in \theta(2^n)$. Conclusión: $T(n) \in \Omega(n)$ y $T(n) \in O(2^n)$. Comprueba las dos en el simulador con «Dos llamadas n/2» y «Dos llamadas n − 1». ## Experimenta con el simulador Carga «3n³ frente a 600n²» y sube la talla máxima. ¿Dónde se cruzan? Cambia 600 por 6000: ¿cómo se mueve el cruce? Carga «Base del logaritmo». ¿A qué constante tiende el cociente? Compárala con $\log_2 10$. Compara $2^n$ con $n^{10}$ en escala logarítmica. ¿A partir de qué talla gana la exponencial? ¿Y con $n^{20}$? Con $b = 2$ y $k = 1$, pon $a = 1$, $a = 2$ y $a = 4$. Mira cómo cambian las barras del árbol: ¿dónde está el coste en cada caso? En Karatsuba, el cociente $T(n)/n^{\log_2 3}$ tiende a una constante. Cambia mentalmente la solución por $n^2$: ¿qué haría el cociente? ## Errores frecuentes * **Dar una cota que no es la más ajustada.** Decir que la búsqueda binaria es $O(n)$ es cierto pero inútil: es $O(\log n)$. * **Confundir $O$ con «peor caso» y $\Omega$ con «mejor caso».** Son cotas de funciones; se usan para el peor y el mejor caso, pero cualquier función tiene las tres. * **Confundir instancia con talla.** Que el algoritmo haga algo distinto cuando $n = 0$ no es una instancia: es un valor de la talla. * **Aplicar el modelo de división a una recurrencia de sustracción**, o al revés. $T(n-1)$ y $T(n/2)$ dan resultados completamente distintos. * **Olvidar el trabajo no recursivo.** En mergesort, la mezcla es lo que da el factor $n$ de cada nivel. * **Creer que $\theta(\log n) \ne \theta(\log_2 n)$.** Todas las bases dan el mismo orden. ## Límites del criterio asintótico La notación asintótica describe tallas **suficientemente grandes**. En la práctica también importan: * **Las constantes ocultas:** un algoritmo teóricamente mejor puede esconder una constante enorme. La multiplicación de matrices de Strassen, $\theta(n^{2{,}81})$, solo compensa con matrices bastante grandes. * **La talla real de los problemas:** si siempre son pequeños, puede ganar el algoritmo asintóticamente peor. * **La memoria:** ganar tiempo suele costar espacio. * **El coste de desarrollo:** si un programa se usa pocas veces, puede compensar uno menos eficiente pero más sencillo. ## Un poco de historia La notación $O$ la introdujo el matemático **Paul Bachmann** en 1894, y **Edmund Landau** la popularizó en teoría de números; por eso se llaman símbolos de Landau. En 1976, **Donald Knuth** propuso usar $\Omega$ y $\theta$ tal como se usan hoy en informática. El teorema que resuelve las recurrencias de división se conoce como **teorema maestro** desde que lo recogió el libro de Cormen, Leiserson, Rivest y Stein (1990), aunque se basa en un trabajo de Bentley, Haken y Saxe de 1980. ## Preguntas frecuentes $O(g)$ es un **conjunto** de funciones, así que lo correcto es $f \in O(g)$. La forma $f = O(g)$ es una costumbre muy extendida, pero no es una igualdad: no se puede leer al revés. El criterio del límite no decide, y hay que volver a la definición. Por ejemplo, $f(n) = n$ para $n$ par y $f(n) = n^2$ para $n$ impar está en $O(n^2)$ y en $\Omega(n)$, pero no en $\theta$ de ninguna de las dos. Porque cada llamada hace dos más, $T(n) = T(n-1) + T(n-2) + c$, y el árbol tiene un número de nodos que crece como $\varphi^n$, con $\varphi \approx 1{,}618$. Está entre $\theta(2^{n/2})$ y $\theta(2^n)$, como se ve acotando por los dos lados. Sí. Todo lo que se dice del coste temporal vale para el espacial: basta con contar celdas de memoria en lugar de pasos. Logarítmico: si $i$ empieza en $n$ y se divide entre 2 hasta llegar a 1, da $\log_2 n$ vueltas. Es lo que pasa en la búsqueda binaria. ## Temas relacionados Análisis experimental: contar operaciones para cada talla. Algoritmos que se resuelven con recurrencias de división. Burbuja, selección, inserción, mergesort y quicksort comparados. This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.