MO417 - Questão para a Prova Oral

Número: 2003-047

Enunciado: Considere um arranjo A de tamanho n, onde todos os elementos são iguais. O que podemos afirmar com relação à complexidade dos algoritmos HeapSort e QuickSort para este caso:

A) HeapSort leva Θ( n lg n ) e QuickSort leva Θ( n² )
B) HeapSort leva Θ( lg n ) e QuickSort leva Θ( n lg n )
C) HeapSort leva Θ( n ) e QuickSort leva Θ( n² )
D) HeapSort leva Θ( n lg n ) e QuickSort leva Θ( n lg n )
E) n.d.a.

Ideia original de: Nielsen Cassiano Simões