1. Use o método mestre para calcular a solução da relação de recorrência T(n)=T\left(\frac{n}{2}\right)+\Theta(1).

Passo 1

O enunciado pede para resolver por meio do Teorema Mestre a recorrência
T(n) \;=\; T\!\bigl(\tfrac n2\bigr)\;+\;\Theta(1).
O Teorema Mestre trata exatamente de recorrências da forma
T(n)=a\,T\!\bigl(\tfrac n b\bigr)+f(n),
identificando a, b e comparando f(n) com n^{\log_b a}.

Passo 2

Aqui temos
a=1,\quad b=2,\quad f(n)=\Theta(1).
Calculamos
n^{\log_b a} \;=\; n^{\log_2 1} \;=\; n^0 \;=\; 1.

Passo 3

Comparamos f(n)=\Theta(1) com n^{\log_b a}=\Theta(1). Logo
f(n)=\Theta\bigl(n^{\log_b a}\bigr)\times\log^0 n,
onde k=0. Isso nos coloca no Caso 2 do Teorema Mestre, que diz:
T(n)=\Theta\bigl(n^{\log_b a}\,\log^{\,k+1}n\bigr).

Passo 4

Substituindo n^{\log_b a}=1 e k=0 obtemos
T(n)=\Theta\bigl(1\cdot\log^{\,0+1}n\bigr)=\Theta(\log n).

Resposta

\Theta(\log n)

Exercícios relacionados