1. Utilize os métodos iterativo e mestre para resolver as seguintes equações abaixo:
  • T(n)=4 T\left(\frac{n}{2}\right)+n
  • T(n)=4 T\left(\frac{n}{2}\right)+n^{2}
  • T(n)=4 T\left(\frac{n}{2}\right)+n^{3}

Passo 1

O enunciado pede para resolver, pelos métodos iterativo e mestre, as recurrences
T(n)=4\,T\bigl(\tfrac n2\bigr)+n,
T(n)=4\,T\bigl(\tfrac n2\bigr)+n^{2} e
T(n)=4\,T\bigl(\tfrac n2\bigr)+n^{3}.
O conteúdo é análise de algoritmos e vamos precisar de:
1. Método iterativo (expansão em árvore de recursão e soma de custos por nível).
2. Teorema mestre (identificar a, b, f(n) e comparar f(n) com n^{\log_b a}).

Passo 2

Resolver iterativamente
\,T(n)=4\,T\bigl(\tfrac n2\bigr)+n.
Cada nível i da árvore tem 4^i subproblemas de tamanho n/2^i.
O custo em cada nó é f\bigl(n/2^i\bigr)=n/2^i, logo o custo total no nível i é
4^i \cdot \frac{n}{2^i} = n\cdot 2^i.
Somando de i=0 até i=\log_2 n:
\sum_{i=0}^{\log_2 n} n\cdot 2^i = n\,(2^{\log_2 n+1}-1) = n\,(2n-1) = \Theta(n^2).
As folhas somam \Theta(4^{\log_2 n})=\Theta(n^2), então
T(n)=\Theta(n^2).

Passo 3

Aplicar o teorema mestre em
\,T(n)=4\,T\bigl(\tfrac n2\bigr)+n.
Aqui a=4, b=2, logo \log_b a=\log_2 4=2. Temos f(n)=n.
Como f(n)=O(n^{2-\varepsilon}) para \varepsilon=1, é o Caso 1 do mestre, daí
T(n)=\Theta\bigl(n^{\log_b a}\bigr) =\Theta(n^2).

Passo 4

Resolver iterativamente
\,T(n)=4\,T\bigl(\tfrac n2\bigr)+n^2.
No nível i, cada nó custa f(n/2^i)=(n/2^i)^2=n^2/4^i e há 4^i nós, então o custo total do nível é
4^i\cdot \frac{n^2}{4^i} = n^2.
Somando de i=0 até \log_2 n (\log_2 n+1)\,n^2=\Theta(n^2\log n). As folhas são \Theta(n^2), de ordem menor. Logo
T(n)=\Theta(n^2\log n).

Passo 5

Aplicar o teorema mestre em
\,T(n)=4\,T\bigl(\tfrac n2\bigr)+n^2.
Temos a=4, b=2, \log_b a=2 e f(n)=n^2=\Theta(n^{2}). É o Caso 2 do mestre, então
T(n)=\Theta\bigl(n^{2}\log n\bigr).

Passo 6

Resolver iterativamente
\,T(n)=4\,T\bigl(\tfrac n2\bigr)+n^3.
No nível i, cada nó custa (n/2^i)^3 = n^3/8^i e há 4^i nós, de modo que o custo do nível é
4^i\cdot \frac{n^3}{8^i} = n^3\bigl(\tfrac12\bigr)^i.
Somando i=0 até \log_2 n resulta em uma série geométrica convergente a 2n^3(1-(1/2)^{\log n+1})=\Theta(n^3). As folhas valem \Theta(n^2), menor ordem. Logo
T(n)=\Theta(n^3).

Passo 7

Aplicar o teorema mestre em
\,T(n)=4\,T\bigl(\tfrac n2\bigr)+n^3.
Aqui a=4, b=2, \log_b a=2 e f(n)=n^3=\Omega(n^{2+\varepsilon}) com \varepsilon=1. Verifica-se a regularidade 4\,f(n/2)\le c\,f(n). É o Caso 3 do mestre, logo
T(n)=\Theta\bigl(f(n)\bigr) =\Theta(n^3).

Resposta

Para cada recorrência temos:
T(n)=4\,T\left(\frac{n}{2}\right)+n\quad \Theta(n^2)
T(n)=4\,T\left(\frac{n}{2}\right)+n^{2}\quad \Theta(n^2\log n)
T(n)=4\,T\left(\frac{n}{2}\right)+n^{3}\quad \Theta(n^3)

Exercícios relacionados