Lectura y Resumen del tema: 3. Characterizing Running Times (Cormen et al., 2022)

Este capítulo explica cómo describir y comparar el tiempo de ejecución de algoritmos según el tamaño de la entrada. Introduce el concepto de funciones de crecimiento, que ayudan a predecir el comportamiento de un algoritmo para entradas grandes.

Se presentan formalmente las notaciones asintóticas:

O (Big-O): cota superior, describe el peor caso.

Ω (Omega): cota inferior, describe el mejor caso.

Θ (Theta): cota ajustada, cuando mejor y peor caso coinciden en orden de crecimiento.

Lectura y Resumen del tema: 3. Notación Asintótica (Brassard & Bratley, 2006)

Este capítulo introduce la notación asintótica como una herramienta para analizar y comparar algoritmos sin necesidad de medir tiempos exactos. El enfoque está en cómo crece el número de operaciones a medida que crece la entrada.

Se explican las notaciones más usadas:

O(f(n)): tiempo no peor que una función f(n).

Ω(f(n)): tiempo no mejor que f(n).

Θ(f(n)): tiempo exactamente en el orden de f(n).

También se mencionan notaciones menos comunes como o(f(n)) (crecimiento estrictamente menor).

El capítulo enfatiza la importancia de comparar algoritmos de forma independiente del hardware, usando estas herramientas para elegir soluciones más escalables.