Use o teorema mestre para derivar um limite assintótico Theta para as seguintes recorrências:
T(n)=16 T(n / 4)+n^2

Passo 1

Vamos entender o que o exercício está pedindo. A gente tem uma recorrência $ T(n) = 16 , T\left(\frac{n}{4}\right) + n^{2} $ e precisa usar o Teorema Mestre para encontrar um limite assintótico $ \Theta $ para $ T(n) $. O Teorema Mestre é uma ferramenta legal que ajuda a resolver recorrências que aparecem em algoritmos de divisão e conquista, comparando alguns termos para determinar como a função se comporta quando $ n $ cresce bastante.

Passo 2

Primeiro, vamos identificar os parâmetros que precisamos para aplicar o Teorema Mestre na nossa recorrência. A forma geral do Teorema Mestre é:
T(n) = a , T(nb) + f(n)
Comparando com o nosso problema:
  • $ a = 16 $
  • $ b = 4 $
  • $ f(n) = n^{2} $

Passo 3

Agora, o próximo passo é calcular $ \log_b a $, que é uma parte importante para determinar qual caso do Teorema Mestre vamos usar. Vamos calcular:
logb a
Isso porque $ 4^{2} = 16 $, então $ \log_{4} 16 = 2 $.

Passo 4

Em seguida, comparamos $ f(n) $ com $ n^{\log_b a} $:
  • $ f(n) = n^{2} $
  • $ n^{\log_b a} = n^{2} $
Então, temos que $ f(n) $ é igual a $ n^{\log_b a} $.

Passo 5

De acordo com o Teorema Mestre, temos três casos:
  1. Se $ f(n) = O\left(n^{\log_b a - \epsilon}\right) $, então $ T(n) = \Theta\left(n^{\log_b a}\right) $.
  2. Se $ f(n) = \Theta\left(n^{\log_b a}\right) $, então $ T(n) = \Theta\left(n^{\log_b a} \log n\right) $.
  3. Se $ f(n) = \Omega\left(n^{\log_b a + \epsilon}\right) $ e certas condições são atendidas, então $ T(n) = \Theta\left(f(n)\right) $.
No nosso caso, como $ f(n) = \Theta\left(n^{2}\right) = \Theta\left(n^{\log_b a}\right) $, estamos no caso 2 do Teorema Mestre.

Passo 6

Aplicando o caso 2, concluímos que:
T(n) = Theta(n^logb a log n) = Theta(n^2 log n)

Resposta

Portanto, o limite assintótico para a recorrência dada é:
T(n) = Theta(n^2 log n)

Exercícios relacionados