1 Departamento de Informática Universidad Técnica Federico Santa María Uso de Función Generatriz Quicksort Prof: Rodrigo Arriagada

2 Rodrigo Alejandro Arriagada Nuñez Fundamentos de Informática II ILI-153 2 Algoritmo Quicksort

3 Rodrigo Alejandro Arriagada Nuñez Fundamentos de Informática II ILI-153 3 Recurrencia Quicksort Veamos otro ejemplo mas complicado. Tomemos la recurrencia que surge cuando se analiza el Quicksort. Vimos antes como invertir la suma, cuando llega hasta n (i.e. t(z)/(1 − z)). En nuestro caso llega hasta n − 1, lo que obliga a un desplazamiento (i.e. zt(z)/(1− z)). La división por n nos hace restarle T (0) = 0, dividir por z e integrar. Transformar n − 1 es facil a partir de la tabla. De modo que tenemos:

4 Rodrigo Alejandro Arriagada Nuñez Fundamentos de Informática II ILI-153 4 Ecuacion diferencial Obtenemos la siguiente ecuación: Resolviendo con Maple o Matlab:

5 Rodrigo Alejandro Arriagada Nuñez Fundamentos de Informática II ILI-153 5 Solución Aplicando series de Taylor: