Use o teorema mestre para derivar um limite assintótico
para as seguintes recorrências:
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 é:
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:
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:
- Se $ f(n) = O\left(n^{\log_b a - \epsilon}\right) $, então $ T(n) = \Theta\left(n^{\log_b a}\right) $.
- Se $ f(n) = \Theta\left(n^{\log_b a}\right) $, então $ T(n) = \Theta\left(n^{\log_b a} \log n\right) $.
- 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:
Resposta
Portanto, o limite assintótico para a recorrência dada é: