MO417 - Questão para a prova oral

Número: 2010-023

Enunciado: No algoritmo quicksort, suponha que o algoritmo de particionamento sempre produza uma divisão desequilibrada de 200 para 1 em todos os níveis de recursão. Seu tempo de execução será dado então pela solução da seguinte recorrência

T(n) = T(200n/201) + T(n/201) + n

e pode ser descrito como:

1. Θ(lg n)
2. Θ(n²)
3. O(n)
4. O(n lg n)
5. NDA

Ideia original de: Maikon Cismoski dos Santos