La notación asintótica es una herramienta fundamental en el análisis de algoritmos. Nos permite describir el comportamiento de un algoritmo en términos de su eficiencia y rendimiento, especialmente cuando el tamaño de la entrada crece hacia el infinito. En esta sección, cubriremos los conceptos básicos de la notación asintótica, incluyendo las notaciones más comunes: O grande (Big O), Ω grande (Big Omega) y Θ grande (Big Theta).

La notación asintótica se utiliza para clasificar algoritmos según su rendimiento y eficiencia. Nos ayuda a entender cómo se comporta un algoritmo a medida que el tamaño de la entrada (n) crece. Las tres notaciones más comunes son:

1. O grande (Big O): Describe el peor caso o el límite superior del tiempo de ejecución de un algoritmo.
2. Ω grande (Big Omega): Describe el mejor caso o el límite inferior del tiempo de ejecución de un algoritmo.
3. Θ grande (Big Theta): Describe el caso promedio o el límite ajustado del tiempo de ejecución de un algoritmo.

La notación O grande se utiliza para describir el límite superior del tiempo de ejecución de un algoritmo. Formalmente, un algoritmo es O(f(n)) si existe una constante c y un valor n₀ tal que para todos los n ≥ n₀, el tiempo de ejecución T(n) ≤ c * f(n).

Ejemplo:

Consideremos un algoritmo cuya complejidad temporal es T(n) = 3n² + 2n + 1. Para este algoritmo, podemos decir que es O(n²) porque, para valores grandes de n, el término n² domina.

En este caso, el algoritmo tiene una complejidad temporal de O(n²).

La notación Ω grande se utiliza para describir el límite inferior del tiempo de ejecución de un algoritmo. Formalmente, un algoritmo es Ω(f(n)) si existe una constante c y un valor n₀ tal que para todos los n ≥ n₀, el tiempo de ejecución T(n) ≥ c * f(n).

Ejemplo:

Para el mismo algoritmo con T(n) = 3n² + 2n + 1, podemos decir que es Ω(n²) porque, para valores grandes de n, el término n² es el mínimo tiempo de ejecución.

La notación Θ grande se utiliza para describir el tiempo de ejecución ajustado de un algoritmo. Formalmente, un algoritmo es Θ(f(n)) si existe una constante c₁ y c₂ y un valor n₀ tal que para todos los n ≥ n₀, c₁ * f(n) ≤ T(n) ≤ c₂ * f(n).

Ejemplo:

Para el mismo algoritmo con T(n) = 3n² + 2n + 1, podemos decir que es Θ(n²) porque el término n² es tanto el límite superior como el límite inferior del tiempo de ejecución.

Dado el siguiente algoritmo, determina su notación O grande:

Solución:

El algoritmo tiene dos bucles anidados, cada uno de los cuales itera n veces. Por lo tanto, la complejidad temporal es O(n²).

Dado el siguiente algoritmo, determina su notación Θ grande:

Solución:

El algoritmo tiene un solo bucle que itera n veces. Por lo tanto, la complejidad temporal es Θ(n).

Dado el siguiente algoritmo, determina su notación Ω grande:

Solución:

El algoritmo tiene dos bucles anidados, pero solo imprime cuando i es igual a j. En el mejor caso, esto ocurre n veces. Por lo tanto, la complejidad temporal es Ω(n).

En esta sección, hemos aprendido sobre la notación asintótica y cómo se utiliza para analizar la eficiencia de los algoritmos. Hemos cubierto las tres notaciones principales: O grande, Ω grande y Θ grande, y hemos visto ejemplos prácticos de cómo aplicarlas. Con esta base, estamos preparados para profundizar en el análisis de la complejidad temporal y espacial en los siguientes módulos.