Teorema Mestre fornece uma metodologia para resolver recorrências da forma T(n) = a T parêntese esquerdo n sobre b parêntese direito mais f parênte...

Teorema Mestre fornece uma metodologia para resolver recorrências da forma T(n) = a T parêntese esquerdo n sobre b parêntese direito mais f parêntese esquerdo n parêntese direito, onde a≥1 e b>1são constantes e f(n) é uma função assintoticamente positiva. Este teorema é particularmente útil na análise de algoritmos de divisão e conquista, permitindo aos cientistas da computação determinar a complexidade de tempo desses algoritmos de uma maneira mais direta. O teorema enuncia três casos baseados na comparação entre f(n) e n à potência de log à potência de a com b à potência de espaço em branco subscrito fim do subscrito fim do exponencial, ajudando a classificar a ordem de crescimento da recorrência. Considere um algoritmo de divisão e conquista com a relação de recorrência T(n) = 2T(n sobre 2) + n. Utilizando o Teorema Mestre, qual das seguintes opções melhor descreve a complexidade de tempo desse algoritmo? Alternativas A) O(n log n) pois a função de trabalho f(n) = né igual a n à potência de log à potência de a com b à potência de espaço em branco subscrito fim do subscrito fim do exponencial, enquadrando-se no caso 2 do Teorema Mestre. B) O(n)pois a função de trabalho domina a recorrência. C) O(log n), pois a profundidade da árvore de recursão é o fator dominante. D) O(n à potência de 1.5 fim do exponencial)pois a combinação dos subproblemas gera um crescimento mais rápido que n. E) O(n ao quadrado), pois o algoritmo precisa resolver duas subproblemas a cada divisão.