Page 216 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Se itera la ecuación unas cuantas veces hasta que sea visible algún patrón de las series que se pre-
senten; de esta forma, tenemos:

Nótese que el patrón de la recurrencia se puede expresar como en la última línea de la ecuación. Si
se itera la ecuación hasta que entonces tenemos y definimos a la
suma Al sustituir estos valores en la ecuación tenemos:

Por propiedad de los logaritmos por lo tanto,

Empleando la notación asintótica, podemos establecer que

entonces

Veamos otro ejemplo. Considérese la siguiente recurrencia:

Al iterar la ecuación se tiene

210