Função de complexidade de algoritmos, cujo tempo de execução...

Alternativa correta: C - f(n) = O(n log n)

Para compreender essa questão, é fundamental ter um bom entendimento sobre complexidade de algoritmos, especialmente em relação a diferentes classes de complexidade e como elas se aplicam a diversos tipos de algoritmos.

A questão aborda especificamente algoritmos que resolvem um problema dividindo-o em problemas menores, resolvendo cada um deles de maneira independente e, depois, combinando as soluções. Esse é um padrão típico de algoritmos de divisão e conquista.

Vamos analisar cada uma das alternativas:

A - f(n) = O(log n)

Esta alternativa refere-se a algoritmos cuja complexidade cresce de forma logarítmica, como a busca binária. No entanto, algoritmos de divisão e conquista, como o Merge Sort ou o Quick Sort, geralmente têm uma complexidade maior devido à necessidade de combinar soluções dos subproblemas.

B - f(n) = O(n)

Esta alternativa se refere a algoritmos com complexidade linear, onde o tempo de execução cresce proporcionalmente ao tamanho da entrada. Exemplos incluem a busca linear em um array. No entanto, isso não se aplica a algoritmos de divisão e conquista, que têm processos adicionais de combinação.

C - f(n) = O(n log n) (Correta)

Algoritmos como o Merge Sort e o Quick Sort possuem essa complexidade. Eles quebram o problema em subproblemas menores (com um custo logarítmico) e combinam as soluções (com um custo linear). Portanto, sua complexidade total é O(n log n).

D - f(n) = O(n²)

Esta alternativa se refere a algoritmos com complexidade quadrática, como o Bubble Sort e o Insertion Sort na pior das hipóteses. Esses algoritmos não seguem o paradigma de divisão e conquista.

Portanto, com base no enunciado e na explicação acima, a alternativa C é a correta, pois reflete adequadamente a complexidade de algoritmos que utilizam o método de divisão e conquista.

c = São algoritmos de complexidade nLogn. Ocorre tipicamente em algoritmos que dividem problemas em problemas menores, porém juntando posteriormente a solução dos problemas menores.

Fonte: https://pt.wikipedia.org/wiki/Complexidade_log-linear

Adescrição é do merge sort, dividir para conquistar. tem complexidade N logN