GabaritoB — O(n log n)
Gabarito: letra B. A complexidade do Merge Sort no pior caso é O(n log n), característica dos algoritmos de ordenação por comparação que utilizam a técnica de divisão e conquista.
O Merge Sort divide recursivamente a lista ao meio (gerando log n níveis) e, em cada nível, realiza a intercalação dos elementos, percorrendo todos os n elementos. Isso resulta em O(n log n) operações no pior, melhor e caso médio, sendo um dos algoritmos de ordenação mais eficientes para grandes volumes de dados.
O(n) é a complexidade linear, típica de algoritmos como busca sequencial ou ordenação por inserção no melhor caso. Não corresponde ao Merge Sort, que possui complexidade superior.
O(n log n) é a complexidade correta do Merge Sort no pior caso. É a melhor complexidade possível para algoritmos de ordenação por comparação.
O(2n) é uma variante linear (constante multiplicativa), ainda O(n). Representa um crescimento linear, não log-linear.
O(n/2) também é linear, apenas com constante menor. Não reflete a necessidade de múltiplos níveis de divisão e conquista.
O(3n) é linear. Qualquer constante multiplicativa não altera a ordem de grandeza, e a complexidade do Merge Sort é superior à linear.
Decore as complexidades dos principais algoritmos de ordenação: Merge Sort e Heap Sort → O(n log n); Quick Sort → O(n²) pior caso (mas O(n log n) médio); Insertion Sort → O(n²) pior caso. Em questões de concurso, o Merge Sort é sempre O(n log n).
Link permanente: /questoes/qg218085