=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
Evaluacion continua - 2023/2024
17 de noviembre de 2023
Ejercicio 6
Borrador
=================================================================

Solucion apartado a
===================

T(n) = 3 T(n/4) + O(n) porque en el peor caso se realizan 3 llamadas recursivas, en
cada una de las cuales la talla del problema se reduce a la cuarta parte, y un bucle
de coste O(n/2) = O(n).

a = 3
b = 4
k = 1
p = 0

Caso a < b^k

Resultado: O(n^k log^p n) = O(n)


Solucion apartado b
===================

T(n) = 2 T(n/4) + O(n) porque en el mejor caso se realizan 2 llamadas recursivas, en
cada una de las cuales la talla del problema se reduce a la cuarta parte, y un bucle
de coste O(n/2) = O(n).

a = 2
b = 4
k = 1
p = 0

Caso a < b^k

Resultado: O(n^k log^p n) = O(n)