Curso 2024/2025
En este ejercicio hay que observar que, aunque en el código aparecen 4 llamadas recursivas, en el peor caso solo se van a ejecutar 3 de ellas. La que no se ejecute no consume tiempo.
Relación de recurrencia: T(n) = 3 T(n/2) + O(1) siendo n la talla del vector.
Podemos resolverla aplicando el Teorema Maestro con a = 3, b = 2, k = 0 y p = 0. Tenemos el caso a > bk, y su solución es T(n) = O(nlog23).