Questão 66864

Um professor de Algoritmos e Estruturas de Dados está lecionando sobre a técnica de 'dividir para conquistar'. Ele quer que os alunos compreendam não apenas a mecânica de algoritmos como o Merge Sort ou o Quick Sort, mas também a análise de sua complexidade através de relações de recorrência. Para isso, ele se baseia no Teorema Mestre (Master Theorem), uma 'receita' para resolver relações de recorrência que surgem de algoritmos de dividir para conquistar. Ele apresenta uma versão simplificada do teorema: "Para uma relação de recorrência da forma $T(n) = aT(n/b) + f(n)$, onde $a$ é o número de subproblemas, $n/b$ é o tamanho de cada subproblema, e $f(n)$ é o custo de dividir o problema e combinar os resultados, podemos comparar $f(n)$ com $n^{\log_b a}$. Se $f(n)$ cresce mais lentamente, a complexidade é dominada pelo número de folhas da árvore de recursão, sendo $\Theta(n^{\log_b a})$. Se $f(n)$ cresce mais rapidamente, a complexidade é dominada pelo custo de combinar, sendo $\Theta(f(n))$. Se ambos crescem na mesma taxa, a complexidade é $\Theta(n^{\log_b a} \log n)$." O professor então descreve o algoritmo de ordenação Merge Sort: ele divide o array de tamanho $n$ em dois subproblemas de tamanho $n/2$, resolve-os recursivamente, e depois combina (merge) os resultados em tempo linear, $O(n)$.

Com base na descrição do Merge Sort e no Teorema Mestre, avalie as seguintes afirmações sobre sua análise de complexidade.

I. A relação de recorrência que descreve o tempo de execução do Merge Sort é $T(n) = 2T(n/2) + O(n)$. Aqui, $a=2$, $b=2$ e $f(n)=O(n)$.

II. Calculando o termo de comparação do Teorema Mestre, temos $n^{\log_b a} = n^{\log_2 2} = n^1 = n$.

III. Comparando $f(n)=O(n)$ com $n^{\log_b a}=O(n)$, vemos que eles crescem na mesma taxa. Portanto, estamos no segundo caso do Teorema Mestre, e a complexidade do Merge Sort é $\Theta(n \log n)$.

É correto o que se afirma em: