Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2024/2025

Solución del ejercicio 19 del tema 1

El coste temporal, en el peor y en el mejor caso, es O(2n), siendo n la cantidad de discos, puesto que la cantidad de llamadas a la función recursiva es 1 + 2 + 4 + 8 + ... + 2n-1 =  i = 0 n - 1 2 i  = 2n - 1 = O(2n) y el tiempo propio de cada llamada es O(1).

El coste espacial, en el peor y en el mejor caso, es O(n), porque puede haber O(n) llamadas activas simultáneamente, y el espacio ocupado por cada una en la pila de llamadas es O(1).