MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Qual das alternativas abaixo é verdadeira?

1. Se utilizarmos um algoritmo Θ(n³)  para encontrar a medianas no SELECT então este não mais terá tempo linear no pior caso
2. Se o QUICKSORT for modificado para realizar o particionamento da mesma forma que o SELECT o faz, então o tempo no pior caso seria O(nlgn)
3. Se o arranjo fosse dividido em 3 grupos o SELECT ainda teria tempo linear no pior caso
4. O SELECT é a melhor opção para se aplicar em problemas práticos
5. NDA

Ideia original de: Anderson Carlos Sousa e Santos