MO417 - Questão para a prova oral

Número: 032

Enunciado:
Considere um algoritmo quicksort com escolha fixa de pivô para partição do vetor de entrada e outro algoritmo que escolhe o pivô aleatoriamente. Não é correto afirmar que:

  1. Os dois algoritmos tem pior caso &Theta(n2).
  2. O algoritmo com escolha aleatória do pivô procura balancear o tamanho dos sub-problemas.
  3. O algoritmo com escolha aleatória do pivô garante custo &Theta(nlgn).
  4. Os dois algoritmos tem caso médio &Theta(nlgn).
  5. NDA

Autor(a): Ricardo Dutra da Silva