MO417 - Questão para a prova oral

Número:

Enunciado: Assinale a alternativa verdadeira sobre o algoritmo SELECT e o algoritmo RANDOMIZED-SELECT.

a) No pior caso do RANDOMIZED-SELECT, todas as partições dividem o arranjo em 2 subarranjos, sendo um com 0 e outro com n-1 elementos. No SELECT, o método para a escolha do pivô não permite este caso.
b) No pior caso o SELECT possui tempo Θ(n) enquanto o randomized possui tempo Θ(nlgn).
c) No SELECT, se o i-ésimo termo for menor que o pivô X, então ele sera buscado no subconjunto com 5 elementos anterior ao subconjunto que contém X.
d) A recursão do SELECT particiona o problema em 5 subproblemas, enquanto que a recursão do RANDOMIZED-SELECT particiona em 2 subproblemas.
e) NDA.

Ideia original de: Jacqueline Midlej do Espírito Santo