MO417 - Questão para a prova oral

Número: 2010-022

Enunciado: Sobre o algoritmo Quicksort, podemos afirmar que:

1. No caso médio o quicksort executa com tempo O(lg n).
2. No pior caso o quicksort tem desempenho tão ruim quanto o mergesort.
3. Seu caso médio é tão bom quanto o melhor caso, ambos com tempo O(n lg n).
4. Seu pior caso ocorre quando a entrada já está ordenada, sendo o tempo de execução O(n lg n).
5. NDA.

Ideia original de: Rodrigo Tripodi Calumby