MMD3101 - Otoño 2025
Profesor: Arturo Merino
Ayudante: Cristian Acevedo
Mergesort
Nos movemos ahora a otro paradigma de diseño de algoritmo llamado dividir para conquistar. Este
paradigma consiste en dividir un problema en subproblemas más pequeños, resolver recursivamente
cada uno de ellos y luego combinar las soluciones para obtener la solución del problema original.
En muchos casos, esto es un metodo sencillo y efectivo para resolver problemas complejos.
Analizar el tiempo en algoritmos de este tipo usualmente nos llevará a resolver relaciones de recu-
rrencia que nos provee una cota recursiva para el tiempo de ejecución del algoritmo. Por otro lado,
su correctitud viene dada por el hecho de que la solución del problema original es una combinación
de las soluciones de los subproblemas.
Vale notar que, usualmente, en los problemas donde se aplica este paradigma, el approach ingenuo
por fuerza bruta ya provee algoritmos que funcionan a tiempo polinomial. En este caso dividir para
conquistar nos permite refinar el tiempo de ejecución en estos problemas. Notemos el contraste con
los problemas que vimos de exploración de grafos y greedy dónde los algoritmos de fuerza bruta
tomaban tiempo exponencial.
Partamos recordando el análisis de un algoritmo que conocemos para el problema de ordenamien-
to: MergeSort.
Ordenamiento
Dado: una lista de n números A = [a1 , a2 , . . . , an ].
Encontrar: una permutación de A que sea no decreciente.
Describamos informalmente MergeSort.
Dividir el input en dos piezas de igual tamaño; resolver los dos subproblemas recur-
sivamente; combinar las soluciones de los subproblemas, gastando tiempo lineal en el
proceso de combinación.
En MergeSort, como es tı́pico en algoritmos recursivos, requerimos también de un caso base: una
solución para problemas de tamaño constante. En el caso de MergeSort, podemos considerar como
caso base n = 2, dónde simplemente ordenamos via una comparación. Notemos que MergeSort toma
efectivamente tiempo lineal al combinar las soluciones de los subproblemas. Esto, pues combinar
dos listas ordenadas de tamaño n toma tiempo O(n).
Por tanto, si T (n) es el tiempo que toma MergeSort en una lista de tamaño n, podemos escribir
la siguiente relación de recurrencia:
l n m j n k
T (n) ≤ T +T + cn
2 2
cuando n > 2, y T (2) = c para alguna constante c. Se simplifica un poco el analisis asumiendo que
n es una potencia de 2.1 En dicho caso la relación de recurrencia se puede escribir como:
n
T (n) ≤ 2T + cn
2
1En la mayorı́a de los casos relevantes, este supuesto no cambia el comportamiento ası́ntotico de la ejecución del
algoritmo. En efecto, basta con “redondear” el tamaño de la entrada a la potencia de 2 más cercana. Esto a lo más
duplica el tamaño y por tanto sólo afecta el tamaño de la entrada en un factor constante.
MMD3101 - Otoño 2025
Profesor: Arturo Merino
Ayudante: Cristian Acevedo
Lema. Sea T : N → N una secuencia tal que
n
T (n) ≤ 2T
+ cn
2
para n > 2 y T (2) = c. Entonces, T (n) = O(n log n) para todo n ≥ 1.
Demostración. Se puede hacer de varias maneras. Una forma es por inducción en n, procederemos
expandiendo la relación de recurrencia. Notemos que dos aplicaciones de la relación de recurrencia
nos dan: n n n n
T (n) ≤ 2T + cn ≤ 2 2T +c + cn = 4T + 2cn
2 4 2 4
En terminos generales, si aplicamos la relación de recurrencia k veces, obtenemos:
n
T (n) ≤ 2k T k + kcn.2
2
n
Luego, para k = log2 2 , tenemos que
n
n n n
T (n) ≤ 2log2 ( 2 ) T (2) + log2 cn = c + c log2 n = O(n log n),
2 2 2
que era lo que querı́amos demostrar. □
Con esto logramos concluir que MergeSort toma tiempo O(n log n) en el peor de los casos.
2En estricto rigor, esto hay que probarlo por inducción.