================================================================= Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I Examen final - 2022/2023 8 de junio de 2023 Ejercicio 1 Borrador ================================================================= Solucion ======== a) Coste temporal en el peor caso: O(n^2) En el peor caso, el dato buscado no esta en el vector y la cantidad de llamadas que se realizan a la funcion recursiva es: O(1 + 2 + 4 + ... + n) = O(n) En cada una se esas llamadas, se invierte tiempo O(n) en crear una copia del vector v completo. El coste temporal total es el resultado de multiplicar la cantidad de llamadas por el coste de copiar el vector en cada llamada. b) Coste temporal en el mejor caso: O(n log n) En el mejor caso, el dato buscado esta en la primera posicion del vector. En cada llamada recursiva, la talla de la zona de busqueda comprendida entre las posiciones inicio y fin se reduce a la mitad. Tras O(log n) llamadas, esa talla llega a 1 y se encuentra el dato, terminando todas las busquedas. En cada una de esas llamadas, se invierte tiempo O(n) en crear una copia del vector v completo. El coste temporal total es el resultado de multiplicar la cantidad de llamadas por el coste de copiar el vector en cada llamada. c) Coste espacial en el peor caso: O(n log n) En el peor caso, hay O(log n) llamadas activas simultaneamente, y por cada una de esas llamadas tenemos en memoria una copia del vector de talla n. d) Coste espacial en el mejor caso: O(n log n) En el mejor caso, por lo dicho en el apartado b, tambien hay O(log n) llamadas activas simultaneamente, y por cada una de esas llamadas tenemos en memoria una copia del vector de talla n. e) Coste temporal en el peor caso pasando v por valor: O(n^2) Si v se pasa por valor, al tiempo O(n) invertido en cada llamada en las lineas 10 y 11 para crear el vector copia se suma otro tiempo O(n) invertido en pasar v por valor. Pero la suma de ambos tiempos sigue siendo O(n) por llamada.