Algoritmos y Estructuras de Datos (VJ1215)

Al igual que en el ejercciio 21.c, si en cada llamada se pasa un vector de talla n por valor, entonces cada llamada consume memoria O(n) y tiempo O(n) para copiar el vector. La memoria de esa copia se libera cuando termina la llamada. Por tanto, tanto en el mejor como en el peor caso:

• al coste temporal hay que añadirle el coste temporal de todas las copias que se realicen, o sea, O(n) multiplicado por la cantidad de llamadas; y

• al coste espacial hay que añadirle O(n) multiplicado por la cantidad de llamadas que pueda haber activas simultáneamente.

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

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

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

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