GabaritoB — θ(n² ) e θ(n lg n ).
Gabarito: letra B. Para o algoritmo Quicksort, a complexidade de pior caso é θ(n²) (ocorre quando as partições são extremamente desbalanceadas, p.ex., vetor já ordenado com escolha de pivô no primeiro elemento), enquanto a complexidade de caso médio é θ(n lg n) (partições razoavelmente balanceadas na média). Esses valores são clássicos e cobrados em provas de algoritmos.
A banca testa se o candidato conhece essas duas ordens e não as confunde. A pegadinha principal é inverter as ordens (alternativa C) ou atribuir valores iguais (alternativas A e D).
Afirma que ambas as complexidades são θ(n²). O pior caso realmente é θ(n²), mas o caso médio do Quicksort é θ(n lg n), e não θ(n²). O erro está no caso médio.
Traz exatamente a combinação correta: pior caso θ(n²) e caso médio θ(n lg n). É a única que corresponde ao conhecimento padrão do algoritmo.
Inverte as ordens: afirma pior caso θ(n lg n) e caso médio θ(n²). Na verdade, é o contrário. Essa é uma armadilha comum: trocar a ordem das duas medidas.
Diz que ambas são θ(n lg n). O pior caso do Quicksort é θ(n²), não θ(n lg n). O caso médio está correto, mas o pior caso não.
Afirma pior caso θ(n lg n) e caso médio θ(n). Ambos estão errados: o pior caso é θ(n²) e o caso médio é θ(n lg n). O valor θ(n) não corresponde a nenhuma das duas.
A banca explora a confusão entre as ordens de pior caso e caso médio. O candidato pode lembrar que o Quicksort tem complexidade O(n²) no pior caso e O(n log n) na média, mas inverter os valores (alternativa C) é o erro mais frequente. Além disso, há quem confunda com outros algoritmos (Heapsort, Mergesort) que têm pior caso O(n log n). Fique atento: a notação θ é exata (limite justo), e o pior caso do Quicksort é realmente θ(n²) — melhor memorizar esse par.
Gabarito: letra B — única que associa pior caso a θ(n²) e caso médio a θ(n lg n).
Link permanente: /questoes/qq337496