Use o teorema mestre para derivar um limite assintótico Theta para as seguintes recorrências:
T(n)=2 T(n / 2)+n-1, para n>1 e T(1)=0

Passo 1

Beleza, vamos resolver esse exercício juntos! A gente vai usar o Teorema Mestre, que é uma ferramenta super útil para resolver recorrências como a que você apresentou. Basicamente, vamos identificar alguns valores na expressão da recorrência e ver qual caso do teorema se aplica para descobrir qual é a ordem de crescimento de $ T(n) $.

Passo 2

Primeiro, vamos identificar os parâmetros da nossa recorrência $ T(n) = 2T(n/2) + n - 1 $:
  • a é o número de subproblemas em que o problema é dividido. Aqui, $ a = 2 $.
  • b é o fator pelo qual o tamanho do problema diminui em cada subproblema. Aqui, $ b = 2 $.
  • f(n) é o custo adicional fora das chamadas recursivas. Neste caso, $ f(n) = n - 1 $. Para simplificar, podemos considerar $ f(n) $ aproximadamente como $ n $.

Passo 3

Agora, precisamos calcular $ \log_b a $, que nos ajuda a comparar $ f(n) $ com $ n^{\log_b a} $:
logb a
Então, $ n^{\log_b a} = n^1 = n $.

Passo 4

Comparamos $ f(n) $ com $ n^{\log_b a} $:
  • $ f(n) = \Theta(n) $
  • $ n^{\log_b a} = n $
Vemos que $ f(n) $ é exatamente do mesmo crescimento que $ n^{\log_b a} $. Isso nos coloca no Caso 2 do Teorema Mestre, onde $ f(n) = \Theta(n^{\log_b a} \log^k n) $ com $ k = 0 $.

Passo 5

De acordo com o Caso 2 do Teorema Mestre, quando $ f(n) $ é proporcional a $ n^{\log_b a} $, a solução da recorrência é:
f(n)
Substituindo os valores que encontramos:
n^logb a

Resposta

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

Exercícios relacionados