GabaritoC — Ω(n lg n).
Gabarito: letra C. O limite inferior para o pior caso de qualquer algoritmo de ordenação por comparação é Ω(n lg n). Esse resultado é clássico e decorre do modelo de árvore de decisão: uma árvore binária com altura h comporta no máximo 2^h folhas, e para que todas as n! permutações sejam possíveis, precisamos que 2^h ≥ n!, o que leva a h = Ω(n lg n). O próprio contexto reforça: "Qualquer algoritmo de ordenação por comparação exige Ω(n lg n) comparações no pior caso" (Teorema 8.1).
A banca cobra o conhecimento teórico fundamental sobre ordenação. As alternativas distratoras exploram valores comuns (n², n, lg n) que aparecem em outros contextos.
Ω(n² lg n) é um limite superior (pior caso) de alguns algoritmos de ordenação por comparação, como o quicksort com partição ruim, mas não é o limite inferior teórico. O menor valor possível para o pior caso é Ω(n lg n), não um valor maior.
Ω(n²) é o pior caso de algoritmos como bubble sort, selection sort e insertion sort, mas não representa o limite inferior para todos os algoritmos de ordenação por comparação. O limite inferior é estritamente menor: Ω(n lg n).
Como demonstrado pelo Teorema 8.1, qualquer algoritmo que ordene apenas por comparações entre elementos precisa realizar pelo menos Ω(n lg n) comparações no pior caso. Esse limite é atingido por algoritmos como merge sort, heap sort (no pior caso) e quicksort (no caso médio).
Ω(n) seria possível se fosse possível determinar a ordenação com um número linear de comparações, mas a análise por árvore de decisão prova que isso é impossível para algoritmos de ordenação por comparação: o número de folhas (n!) cresce mais rápido que 2^{cn} para qualquer constante c.
Ω(lg n) é o limite inferior para problemas como busca em um vetor ordenado (busca binária), não para ordenação. A ordenação exige comparar pares de elementos suficientes para determinar a permutação completa, o que requer pelo menos Ω(n lg n) comparações.
Para memorizar o limite inferior, lembre-se do teorema: qualquer ordenação por comparação requer Ω(n log n) no pior caso. Compare com os limites de outros problemas: busca em vetor ordenado (Ω(log n)), encontrar o mínimo (Ω(n)).
Gabarito: letra C.
Link permanente: /questoes/qq337494