MO417 - Questão para a prova oral

Número: 023

Enunciado: No algoritmo quicksort, suponha que o algoritmo de particionamento sempre produza uma divisão desequilibrada de 200 para 1 em todo nível de recursão, dado pela seguinte recorrência T(n) = T(200n/201) + T(n/201) + n. O tempo de execução do quicksort será de?

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

Autor(a): Maikon Cismoski dos Santos