3.3.3. Búsqueda del máximo y del mínimo.
Comparaciones (entre valores del array) usando divide y vencerás. Debemos resolver la ecuación de recurrencia:
Con condiciones iniciales:
Suponiendo n = 2k, tenemos:
t(k) = 2·t(k-1) + 2 ? (x-2)·(x-1) = 0 ? t(n) = C1n + C2
Aplicando las condiciones iniciales obtenemos:
Asignaciones. La ecuación de recurrencia es la misma, sólo cambian las condiciones iniciales.
El número de comparaciones es menor en el caso promedio.
El número de asignaciones es peor en todos los casos.