MO417 - Questão para a prova oral

Número: 2009-001

Enunciado: Sobre o algoritmo de ordenação Merge-Sort recursivo, é INCORRETO afirmar que:

1. Seu tempo de execução pode ser descrito por uma equação de recorrência.
2. A etapa de dividir o problema em subproblemas tem tempo de execução linear (Θ(n)).
3. Considerando a complexidade de pior caso, é assintoticamente mais eficiente que o Insertion-Sort (ordenação por inserção).
4. Podemos usar ferramentas matemáticas para resolver sua equação de recorrência e estabelecer limites sobre o desempenho do algoritmo.
5. NDA

Ideia original de: Renato Hirata