MO417 - Questão para a prova oral

Número: 030

Enunciado: Utilizando uma seleção da mediana que no pior caso é O(n) para realizar a escolha do pivô no Quick-Sort, e distribuindo igualmente entre as particoes os elementos iguais ao pivo, podemos afirmar que:

1. O tempo de execução do Quick-Sort no melhor caso será O(n).
2. O tempo de execução do Quick-Sort no pior caso será O(n).
3. O tempo de execução do Quick-Sort no pior caso será O(n lg n).
4. O tempo de execução do Quick-Sort no pior caso poderá ser Ω(n²).
5. NDA

Autor(a): Filipe Areias Névola