MO417 - Questão para a prova oral

Número: 2010-027

Enunciado: Temos um vetor de tamanho n para ser ordenado, onde cada elemento é um inteiro pertencente ao intervalo [0,k). Seja f o custo de ordenação de tal vetor através do Counting Sort, em função de n e k. Marque a alternativa INCORRETA:

1. Se k for ω(n) então f é Ω(n), mas não é Θ(n)
2. Se k for Ω(n) então f é Θ(n)
3. Se n for ω(k) então f é Θ(n)
4. Se n for Ω(k) então f é Θ(n)
5. NDA

Ideia original de: Daniel Cason