4.3.1 AL/Análisis Básico de Algoritmos. (4 horas)

Tópicos

• Análisis asintótico de límites en los casos promedio y superior.
• Identificar la diferencias entre el comportamiento entre el mejor, mediano y peor caso.
• Notación Big $O$, little $o$, Omega $\Omega$ y Theta $\Theta$.
• Clases de complejidad estándar.
• Medición empírica de desempeńo.
• Puntos de equilibrio entre tiempo vs espacio en algoritmos.
• Uso relaciones de recurrencia para el análisis de algoritmos recursivos.

Objetivos

• Explicar el uso de las notaciones Big O, Omega $\Omega$ y Theta $\Theta$ para describir la cantidad de trabajo hecha por un algoritmo.
• Uso de notaciones Big $O$, Omega $\Omega$ y Theta $\Theta$ para determinar los límites asintóticos superior, inferior y el más próximo en tiempo y espacio en complejidad de algoritmos .
• Determinar la complejidad de tiempo y espacio de algoritmos simples.
• Deducir la relación de recurrencia que describe la complejidad de tiempo de algoritmos definidos recursivamente.
• Solucionar relaciones de recurrencia elemental.