MO417 - QUESTÃO PARA PROVAL ORAL

Número:

Enunciado: Dada uma sequência de entrada <a₁, a₂,...,an>. Sobre o tempo de execução (T(n)) do Quicksort é possível afirmar:

1. Se an > ai então T(n) = Θ(n²), para i = {1...n-1}
2. Se ai = ai+1 então T(n) = Θ(nlgn), para i = {1...n-1}
3. Se ai < ai+1 então T(n) = Θ(n), para i = {1...n-1}
4. Se ak < an < a(n/2)+k então T(n) = O(n lg n), para k = {1...(n/2)-1}
5. NDA

Ideia original de: Anderson Carlos Sousa e Santos