Algoritmos y Estructuras de Datos (VJ1215)

Sea n la talla del vector a ordenar.

(a) Mezclando con coste O(n):

Relación de recurrencia: T(n) = 2 T(n/2) + O(n)

Variables: a = 2, b = 2, k = 1 y p = 0

Caso: a = b^k

Solución: T(n) = O(n log n)

(b) Mezclando con coste O(n log n):

Relación de recurrencia: T(n) = 2 T(n/2) + O(n log n)

Variables: a = 2, b = 2, k = 1 y p = 1

Caso: a = b^k

Solución: T(n) = O(n log² n)

(c) Mezclando con coste O(n²):

Relación de recurrencia: T(n) = 2 T(n/2) + O(n²)

Variables: a = 2, b = 2, k = 2 y p = 0

Caso: a < b^k

Solución: T(n) = O(n² log⁰ n) = O(n²)