MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Sobre a seleção de um elemento em uma sequência, escolha a alternativa incorreta:
a. A seleção de um elemento, quando aleatorizado, ocorre em tempo esperado O(n).
b. A seleção randomizada possui tempo O(n²) no pior caso.
c. O problema da seleção tem tempo teórico O(n) no pior caso.
d. O processo de escolha do pivô, sendo baseado no do quicksort randômico, também ocorre em tempo O(n).
e. NDA

Ideia original de: Jorge Augusto Hongo