GabaritoD — 0(n²)
Gabarito: letra D. No pior caso, o algoritmo Quicksort com escolha do primeiro elemento como pivô apresenta complexidade assintótica O(n²). Isso ocorre quando o vetor já está ordenado (ou inversamente ordenado), gerando partições desbalanceadas de tamanhos 0 e n-1, resultando na recorrência T(n) = T(n-1) + Θ(n), cuja solução é Θ(n²). O material de apoio confirma: "Este método decai para O(n2) quando o array já está ordenado ou quando só possui elementos iguais."
O(n) é a complexidade linear, típica de algoritmos como busca sequencial ou ordenação Counting Sort, não do Quicksort no pior caso.
O(log n) é a complexidade de algoritmos como busca binária, não se aplica ao Quicksort.
O(n log n) é a complexidade do caso médio e do melhor caso do Quicksort, quando as partições são equilibradas. No pior caso, a complexidade é superior.
Exatamente O(n²), conforme explicado: partições desbalanceadas levam a níveis de recursão proporcionais a n, com custo linear em cada nível, totalizando Θ(n²).
O(n³) é uma complexidade cúbica, típica de algoritmos mais lentos (ex.: multiplicação ingênua de matrizes), não do Quicksort.
Gabarito: letra D
Link permanente: /questoes/qg686035