MO417 - Questão para a prova oral

Número: 2010-020

Enunciado: Assinale a alternativa incorreta:

1. O Heapsort possui tempo de execução O(n log n) apenas para arranjos ordenados em ordem decrescente, já que a estrutura do heap está praticamente "montada".
2. O Quicksort e o Insertion-Sort possuem complexidade O(n²) para o pior caso.
3. O Quicksort se mostra mais eficiente que o Insertion-Sort pois seu tempo de execução no caso médio é Θ(n log n).
   
4. Se os sucessivos particionamentos do arranjo são balanceados, o Quicksort é executado assintoticamente tão rápido quanto a ordenação por intercalação.
5. NDA

Ideia original de: Matheus Silva Mota