Cálculo de complejidad de una función recursiva

Generalmente las funciones recursivas, por su funcionamiento de llamadas a sí mismas, requieren mucha mayor cantidad de recursos (memoria y tiempo de procesador) que los algoritmos iterativos.

Un método para el cálculo de la complejidad de una función recursiva consiste en calcular la complejidad individual de la función y después elevar esta función a n, donde n es el número estimado de veces que la función deberá llamarse a sí misma antes de llegar al caso base.

Fuente: Apunte Análisis, diseño e implantación de algoritmos de la facultad de contaduría y administración, UNAM