Notación asintótica: O, Omega, Theta

---

Notación asintótica

Definición

Es una herramienta matemática utilizada para describir la eficiencia de un algoritmo en términos de su comportamiento cuando el tamaño de la entrada tiende a crecer hacia el infinito.

Descripción

1. Se centra en analizar cómo cambian los recursos requeridos, como el tiempo o la memoria, en función del tamaño de la entrada, ignorando constantes y factores menores para obtener una representación simplificada.

2. Es importante porque:

• Permite comparar diferentes algoritmos de manera objetiva.
• Ayuda a seleccionar el algoritmo más eficiente para un problema dado, especialmente con grandes cantidades de datos.
• Es crucial en el diseño de sistemas y aplicaciones que requieren optimización de rendimiento.

 3. Permite responder a preguntas como:

• ¿El algoritmo se vuelve lento cuando aumenta el tamaño de la entrada?
• ¿El algoritmo mantiene un tiempo de ejecución rápido cuando aumenta el tamaño de la entrada?

Principales notaciones asintóticas

1. Notación O grande (O)
2. Notación Ω grande (Ω, omega)
3. Notación Θ (Theta)

---

Notación asintótica Omega

Definición

• Describe el mejor caso de un algoritmo.
• Representa el límite inferior del tiempo de ejecución.

Descripción

Ejemplos

Si un algoritmo tiene Ω(n) significa que, en el mejor caso, el algoritmo requiere al menos un tiempo proporcional al tamaño de la entrada.

---

Notación asintótica O

Definición

Hace referencia a la velocidad de crecimiento de los valores de una función.

Tiempo de ejecución T(n) de un programa es O\(n^2\)

Esto indica que existen constantes enteras positivas c y \(n_0\) tales que para n ≥ \(n_0\), T(n) ≤ c\(n^2\)

• Describe el peor caso de un algoritmo.
• Representa el límite superior del tiempo de ejecución o consumo de recursos.

Descripción

Ejemplos

• Si un algoritmo tiene O\(n^2\), significa que su tiempo de ejecución crece como máximo proporcional al cuadrado del tamaño de la entrada.

---

Notación asintótica Theta

Definición

• Describe el caso promedio o el comportamiento exacto en términos de límites superior e inferior.
• Representa el rango exacto en el que se encuentra el tiempo de ejecución del algoritmo.

Descripción

Ejemplos

Si un algoritmo tiene Θ(n) significa que su tiempo de ejecución crece proporcionalmente al tamaño de la entrada.

Referencias

Aho, Alfred, Ullman, Jeffrey, et al. Data Structures and Algorithms, New Jersey Addison-Wesley, 1983