Algoritmos y Estructuras de Datos (VJ1215)

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

Justificación:

El árbol de llamadas recursivas tiene O(log n) niveles.

La suma de tiempos es O(n) por cada nivel, porque crear 2 vectores de talla n/2 cuesta O(n) en total, crear 4 vectores de talla n/4 cuesta O(n) en total, crear 8 vectores de talla n/8 cuesta O(n) en total, etc.

La suma de tiempos total se obtiene multiplicando ambos resultados.

Un análisis idéntico aparecerá en el tema 5.2 cuando estudiemos el algoritmo de ordenación Mergesort como ejemplo de aplicación de la estrategia Divide y Vencerás. En ese tema aprenderemos también a realizar el análisis utilizando el Teorema Maestro.

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

Justificación:

No todas las llamadas están activas simultáneamente. Llamadas activas simultáneamente solo puede haber una de cada nivel: una con 2 vectores locales de talla n/2, una con 2 vectores locales de talla n/4, una con 2 vectores locales de talla n/8, etc.

La suma del espacio ocupado por los vectores que están simultáneamente en memoria es O(n + n/2 + n/4 + ... + 1) = O(n).