# Notación asintótica y recurrencias > O, Ω y θ de dos costes con el límite del cociente, c y n₀ de la definición, y recurrencias de sustracción y división con su árbol de llamadas. - Página interactiva: https://simulab.es/programacion/notacion-asintotica - Asignatura: [Programación](https://simulab.es/programacion.md) - Niveles: [Universidad](https://simulab.es/universidad.md) - Gratis, en español y en el navegador, sin registro. ## Qué es y cómo se usa La notación asintótica compara cómo crece el coste de un algoritmo con la talla del problema, sin fijarse en las constantes ni en las tallas pequeñas. f ∈ O(g) significa que, a partir de un n₀, f(n) ≤ c·g(n): g es una cota superior. Ω es la cota inferior y θ el orden exacto, cuando se cumplen las dos. En la primera pestaña escribes dos costes y el simulador calcula el límite de su cociente, que decide la relación: una constante distinta de cero da θ, infinito da Ω y cero da O. También busca la c y el n₀ de la definición y el punto en que las dos curvas se cruzan. La segunda pestaña resuelve recurrencias de sustracción, T(n) = a·T(n − b) + c·nᵏ, y de división, T(n) = a·T(n/b) + c·nᵏ, con la tabla de modelos generales. El árbol de llamadas muestra el coste de cada nivel: si manda la raíz, si todos cuestan lo mismo o si mandan las hojas. ## Ejemplo resuelto **Mergesort divide el vector en dos mitades, se llama en cada una y mezcla en tiempo lineal. ¿Cuál es su coste?** 1. Recurrencia: T(n) = 2·T(n/2) + c·n, modelo de división con a = 2, b = 2 y k = 1. 2. Se compara a con bᵏ: 2 = 2¹, así que estamos en el caso a = bᵏ. 3. Cada nivel del árbol cuesta c·n y hay log₂ n niveles. 4. T(n) ∈ θ(nᵏ·log n) = θ(n log n). **Solución:** T(n) ∈ θ(n log n) ## Preguntas frecuentes ### ¿Por qué no importa la base del logaritmo? Porque log_a n / log_b n = log_a b, una constante. Cambiar de base solo multiplica por una constante, y las constantes no cambian el orden. Por eso se escribe simplemente log n. ### Si 3n³ es peor que 600n², ¿por qué a veces conviene? Porque la notación asintótica habla de tallas grandes. 3n³ solo supera a 600n² a partir de n = 200; si los problemas reales son más pequeños, el algoritmo cúbico es más rápido. ### ¿Cuál es la diferencia entre O y θ? O es solo una cota superior: 3n + 2 está en O(n), pero también en O(n²). θ es el orden exacto: 3n + 2 está en θ(n) y no en θ(n²). Siempre se da la cota más ajustada. ### ¿Puedo usar la tabla de recurrencias en el examen? Normalmente no: la complejidad hay que obtenerla resolviendo la recurrencia, por ejemplo por sustitución. La tabla sirve para comprobar que el resultado es correcto. ## Herramientas relacionadas - [Ley de Amdahl y Gustafson](https://simulab.es/programacion/ley-de-amdahl.md): Speedup, eficiencia, coste y sobrecarga de un programa paralelo según su fracción paralelizable y el número de procesadores. - [Tablas hash](https://simulab.es/programacion/tablas-hash.md): Tabla cerrada con sondeo lineal o cuadrático y abierta con listas, en Java: colisiones, borrados, factor de carga y redimensionado. - [ArrayList y lista enlazada](https://simulab.es/programacion/listas.md): Las dos listas en Java paso a paso: capacidad y crecimiento, desplazamientos, recorrido de nodos y coste de cada operación. - [Árbol binario enhebrado](https://simulab.es/programacion/arbol-enhebrado.md): Hilos al sucesor y al predecesor en inorden, y recorrido del árbol en Java sin recursión ni pila. - [Memoria y punteros en C](https://simulab.es/programacion/punteros.md): Programas en C línea a línea con la pila, el montón y a dónde apunta cada puntero: paso por valor y por referencia, malloc y free. - [Recursión en C](https://simulab.es/programacion/recursion.md): Potencia, factorial, MCD, Fibonacci y suma de un vector: pila y árbol de llamadas, descenso y ascenso, y su versión iterativa. - [Divide y vencerás](https://simulab.es/programacion/divide-y-venceras.md): Máximo, suma, vector creciente y búsqueda binaria en C: el trozo de cada llamada, el árbol de subproblemas y su coste. - [Backtracking](https://simulab.es/programacion/backtracking.md): Mochila 0/1 y descomposición en sumandos en C: árbol de búsqueda con podas, todas las soluciones, una o la óptima. Más herramientas: [todas las de Simulab](https://simulab.es/llms.txt).