MO417 - Questão para a prova oral

Número: 048

Enunciado:
Com relação aos algoritmos que selecionam o i-ésimo menor elemento de um vetor, é correto afirmar que:

1. A complexidade para encontrar o i-ésimo elemento do vetor é O(n) no pior caso, independente do algoritmo utilizado
2. É possível encontrar o i-ésimo elemento de um vetor completamente ordenado em tempo constante
3. Não é possível encontrar o i-ésimo menor elemento sem ordenar o vetor
4. O i-ésimo elemento de um vetor ordenado é sempre igual à mediana do vetor
5. NDA

Autor(a): Fabio Nagamine