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

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.
logb a
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:
f(n) = n
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:
f(n) = O(n^logb a - varepsilon)
Aplicando isso ao nosso caso:
varepsilon > 0

Resposta

A solução assintótica para a recorrência é $ T(n) = \Theta(n^2) $.

Exercícios relacionados