Relación de recurrencia

En matemática, una relación de recurrencia es una ecuación que define una secuencia recursiva; cada término de la secuencia es definido como una función de términos anteriores.

An alisis de algoritmos recursivos
Cuando analizamos algoritmos recursivos es util describir la funci on de coste como una recurrencia.
Una recurrencia es una ecuaci on que describe una funci on en t erminos del propio valor de la funci on para argumentos m as cercanos a alg un caso b asico, para el que la funci on est a de nida expl citamente. Resolver una recurrencia signi ca encontrar la expresi on expl cita que de ne la funci on recurrente. Generalmente, nos bastar a con clasi car la funci on recurrente en una notaci on asint otica

La recurrencia en la computación

La conexión con el análisis de algoritmos estriba en que la forma que se ha adoptado para medir las complejidades, utiliza funciones cuyo dominio son los números naturales, o en otras palabras, sucesiones. Si el algoritmo es recurrente, es de esperarse que las complejidades, como funciones que estiman la demanda de recursos a lo largo de la ejecución, sean sucesiones que satisfacen ciertas ecuaciones de recurrencia. En un algoritmo recursivo, la función t(n) que establece su complejidad viene dada por una ecuación de recurrencia. Una ecuación de recurrencia nos permiten indicar el tiempo de ejecución para los distintos casos del algoritmo recursivo (casos base y recursivo).

Resoluci on de recurrencias mediante la t ecnica de expansi on

Ejemplo: Dada la recurrencia

De T(n/2)= T(n/2^2)+b obtenemos T(n)=T(n/2^2)+b+b

)

Repita la sustituci on correspondiente alguna vez m as, hasta que sea capaz de "adivinar" un expresi on patr on que generalice todas las sustituciones sucesivas.

T(n) =T(n/2^2) +b+b=T(n/2^3) +b+b+b=...=T(n/2^i) +ib

 Supongamos que las raices son: r1,...,rk.

Entonces la soluci on de la recurrencia es de la forma:

 Para encontrar los valores de las constantes c1,...,ck hay que establecerun sistema de ecuaciones con k casos particulares. Para las recurrencias no homogeneas, adem as aparece la ra i z b (de la parte derecha de la ecuaci on) con multiplicidad d+ 1 siendo del grado del polinomio p(n). Cuando hay una ra iz multiple rj, de multiplicidad m, entonces en la soluci on deben aparecer los sumandos siguientes: