Questão de Lógica de Programação e Estrutura de Dados · CESGRANRIO BASA 01/2024 (nº 31)

Conceito-chave: Complexidade de pior caso mede o tempo máximo que um algoritmo leva para ordenar qualquer entrada. Para escolher o mais seguro sem saber os dados, você compara esse limite máximo: Mergesort e Heapsort garantem $O(n \log n)$ sempre, enquanto Inserção e Bubblesort podem degradar para $O(n^2)$ no pior caso.

• (A) Incorreta: Inserção e Bubblesort têm pior caso $O(n^2)$, muito pior que $O(n \log n)$, então não são a escolha ótima.
• (B) Incorreta: Inserção tem pior caso $O(n^2)$, enquanto Mergesort tem $O(n \log n)$; juntos não representam a menor complexidade possível.
• (C) Correta: Mergesort e Heapsort são os únicos com pior caso garantido $O(n \log n)$, o menor entre os quatro, independentemente do tamanho ou ordem inicial dos dados.
• (D) Incorreta: Bubblesort tem pior caso $O(n^2)$, então não atende ao critério de menor complexidade.
• (E) Incorreta: Bubblesort tem pior caso $O(n^2)$, descartando-o; Mergesort sozinho não forma o par correto.

Armadilha da banca (distrator mais tentador – B): Muitos alunos lembram que Inserção é rápido em dados quase ordenados (melhor caso $O(n)$), mas a questão pede pior caso, não melhor. A pegadinha é confundir "bom em casos específicos" com "garantia de pior caso". Inserção, no pior caso (dados invertidos), faz $O(n^2)$, então não pode ser selecionada.