Algoritmos y Estructuras de Datos (VJ1215)

El coste temporal, en el peor y en el mejor caso, es O(2ⁿ), siendo n la cantidad de discos, puesto que la cantidad de llamadas a la función recursiva es 1 + 2 + 4 + 8 + ... + 2^n-1 =  $\sum _{i=0}^{n-1}{2}^i$ = 2ⁿ - 1 = O(2ⁿ) 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).