Algoritmos y Estructuras de Datos (VJ1215)

El coste temporal y espacial crece al crecer el exponente. En los siguientes resultados llamaremos n al exponente.

Coste temporal en el peor caso: O(n).

Coste temporal en el mejor caso: O(n).

Coste espacial en el peor caso: O(log n).

Coste espacial en el mejor caso: O(log n).

El coste temporal, en el peor y en el mejor caso, es O(n), porque se realizan 1 + 2 + 4 + 8 + ... + 2·n = 4·n - 1 = O(n) llamadas a la función recursiva, y el tiempo propio de cada llamada es O(1).

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

Los dos costes temporales mejorarían, reduciéndose a O(log n), si no se repitiese dos veces la misma llamada recursiva, como se muestra en la solución del ejercicio 9.