Suponha que, ao invés de dividir em duas partes, foi criada uma versão do merge-sort que divida a entrada em quatro partes, ordene cada quarta-part...

O algoritmo do merge-sort que divide a entrada em quatro partes, ordena cada quarta-parte e combina as quatro partes usando um procedimento O(n) pode ser descrito da seguinte forma: 1. Divida a entrada em quatro partes iguais. 2. Ordene cada uma das quatro partes separadamente. 3. Combine as quatro partes ordenadas usando um procedimento linear O(n). A equação de recorrência que descreve o tempo de execução desse algoritmo é T(n) = 4T(n/4) + O(n), onde: - T(n) representa o tempo de execução para uma entrada de tamanho n. - 4T(n/4) representa o tempo gasto para ordenar as quatro partes. - O(n) representa o tempo gasto para combinar as quatro partes de forma linear. A complexidade desse algoritmo é O(n log n), pois a divisão em quatro partes e a combinação linear não alteram a complexidade do merge-sort, que é dominada pela etapa de ordenação das partes.