=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
Examen final - 2022/2023
24 de enero de 2023
Ejercicio 1
Borrador
=================================================================


Solucion
========

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

En el peor caso, el dato buscado no esta en el vector y, hasta llegar al caso base, en
cada llamada a la funcion recursiva se crea un nuevo vector, pero solo uno: izquierda o
derecha.  La talla de ese vector se reduce a la mitad en cada llamada, y la suma de los
tiempos invertidos en crear esos vectores en todas las llamadas es:

O(n/2 + n/4 + n/8 + ... + 1) = O(n).


b) Coste espacial en el peor caso: O(n)

En el peor caso, la suma de la memoria ocupada por los vectores considerados en el
apartado a es tambien:

O(n/2 + n/4 + n/8 + ... + 1) = O(n).


c) Coste espacial en el peor caso sin contar el coste de los vectores: O(log n)

Como la talla de los vectores se va reduciendo a la mitad en cada llamada, en el peor caso
la cantidad de llamadas activas simultaneamente es O(log n).  Sin contar el espacio
ocupado por los vectores, el restante coste espacial propio de cada llamada es O(1).


d) Coste temporal en el peor caso pasando v por valor: O(n)

Al pasar v por valor, en cada llamada se realiza una copia de lo que estamos pasando.  La
suma de los tiempos invertidos en realizar esas copias en todas las llamadas es:

O(n + n/2 + n/4 + ... + 1) = O(n)

Eso se suma al coste temporal O(n) de crear los vectores izquierda o derecha, analizado en
el apartado a. El coste total sigue siendo O(n).


e) Coste espacial en el peor caso pasando v por valor: O(n)

Al pasar v por valor, cada llamada recibe una copia. La memoria que ocupan esas
copias es:

O(n + n/2 + n/4 + ... + 1) = O(n)

Eso se suma al coste espacial O(n) de los vectores izquierda o derecha, analizado en el
apartado b. El coste total sigue siendo O(n).