Use o teorema mestre para derivar um limite assintótico
para as seguintes recorrências:
Passo 1
Beleza! Vamos resolver essa recorrência usando o Teorema Mestre. A gente tem a relação $ T(n) = 9T\left(\frac{n}{3}\right) + n $. Isso pertence ao campo de Análise de Algoritmos, especificamente para resolver recorrências que aparecem em algoritmos de divisão e conquista. Para resolver, vamos identificar os valores de $ a $, $ b $ e $ f(n) $ na fórmula padrão do Teorema Mestre e comparar as funções envolvidas.
Passo 2
Primeiro, vamos identificar os parâmetros da nossa recorrência em relação à fórmula geral do Teorema Mestre, que é $ T(n) = aT\left(\frac{n}{b}\right) + f(n) $.
Aqui, temos:
- $ a = 9 $: número de subproblemas.
- $ b = 3 $: fator pelo qual o problema é dividido.
- $ f(n) = n $: custo extra além das chamadas recursivas.
Passo 3
Agora, vamos calcular $ \log_b a $, que é essencial para determinar qual caso do Teorema Mestre se aplica.
Isso porque $ 3^2 = 9 $.
Passo 4
Com $ \log_b a = 2 $, precisamos comparar $ f(n) $ com $ n^{\log_b a} $, que no caso é $ n^2 $.
Temos que:
- $ f(n) = n $
- $ n^{\log_b a} = n^2 $
Agora, vamos ver como $ f(n) $ se comporta em relação a $ n^2 $.
Passo 5
Observamos que $ f(n) = n $ cresce mais devagar que $ n^2 $. Em termos de notação assintótica, isso significa que:
Onde $ \varepsilon = 1 $, já que $ n = n^{2 - 1} $.
Passo 6
Segundo o Teorema Mestre, se $ f(n) = O(n^{\log_b a - \varepsilon}) $ para algum $ \varepsilon > 0 $, então:
Aplicando isso ao nosso caso:
Resposta
A solução assintótica para a recorrência é $ T(n) = \Theta(n^2) $.