Asymptotic analysis of recurrence relations in "divide and conquer" algorithms

Este Trabajo de Fin de Grado se enfoca en el análisis de algoritmos recursivos utilizando técnicas matemáticas para resolver recurrencias. El objetivo principal del trabajo es presentar diferentes métodos para estudiar recurrencias propias de los algoritmos Divide y Vencerás, utilizando como herramientas el Teorema Maestro y el Teorema de Akra-Bazzi. El trabajo se inicia con una exposición de los conceptos preliminares necesarios, incluyendo la notación asintótica, una introducción general a las recurrencias y una descripción de la estrategia Divide y Vencerás. A continuación, se presenta el Teorema Maestro, que ofrece un enfoque sistemático para resolver recurrencias que surgen en particiones homog éneas. Posteriormente, se estudia el Teorema de Akra-Bazzi, el cual extiende el análisis a casos con subproblemas de tamaño no uniforme. Finalmente, se exponen dos generalizaciones de este último resultado, orientadas a ampliar su aplicabilidad: una mediante la relajación de algunas de sus condiciones iniciales, y otra mediante una reformulación más general que permite abordar recurrencias con divisiones no exactas, incrementando así la flexibilidad del marco analítico propuesto.