Questão 2 (2 pts) - Resolva as seguintes relações de recorrência:
\mathrm{S}(\mathrm{n})=4 \mathrm{~S}(\mathrm{n} / 2)+\mathrm{n}^{2}, \mathrm{~S}(1)=1

Passo 1

O enunciado dá a recorrência
S(n)=4\,S\!\left(\dfrac{n}{2}\right)+n^{2},\qquad S(1)=1.
O que se pede é resolver essa relação de recorrência, ou seja, encontrar uma expressão fechada para S(n) válida (supondo que n permite dividir por 2 repetidas vezes). Informações relevantes que o enunciado deu:
  • A recorrência usa n/2, logo é natural assumir que n é potência de 2 (caso contrário a fórmula precisa de ajuste por piso/ceiling).
  • O termo não homogêneo é n^{2}.
  • A condição inicial é S(1)=1.

Passo 2

Primeiro passo técnico: substituir n por uma potência de 2. Defina n=2^{m} com m\in\mathbb{Z}_{\ge 0}. Isso facilita porque dividir n por 2 corresponde a diminuir m em 1.
Defina a sequência dependente de m:
A(m)=S(2^{m}).
Agora reescrevemos a recorrência em termos de A(m). Substituindo n=2^{m} em S(n)=4S(n/2)+n^{2} obtemos:
A(m)=4\,A(m-1)+ (2^{m})^{2}.
Como (2^{m})^{2}=2^{2m}=4^{m}, a recorrência fica
A(m)=4\,A(m-1)+4^{m}, \qquad A(0)=S(1)=1.

Passo 3

Temos agora uma recorrência linear não-homogênea de ordem 1:
A(m)-4A(m-1)=4^{m}.
Para resolver, procedemos pelo método clássico: encontrar a solução geral da homogênea e uma solução particular da não-homogênea.
A equação homogênea associada é
A_{\text{h}}(m)-4A_{\text{h}}(m-1)=0,
cuja solução é da forma
A_{\text{h}}(m)=C\cdot 4^{m},
onde C é constante arbitrária (porque 4^{m} é raiz característica).

Passo 4

Agora precisamos de uma solução particular A_{\text{p}}(m) para
A(m)-4A(m-1)=4^{m}.
Observação: o termo do lado direito é 4^{m}, que é solução da homogênea (ressonância). Nesses casos normalmente multiplicamos pela potência de m. Tentamos uma solução particular da forma
A_{\text{p}}(m)=k\,m\,4^{m},
onde k é uma constante a determinar.
Vamos calcular o lado esquerdo com essa hipótese:
A_{\text{p}}(m)-4A_{\text{p}}(m-1) = k\,m\,4^{m} - 4\cdot k\,(m-1)\,4^{\,m-1}.
Note que 4\cdot 4^{\,m-1}=4^{m}, então
A_{\text{p}}(m)-4A_{\text{p}}(m-1) = k\,m\,4^{m} - k\,(m-1)\,4^{m} = k\cdot 4^{m}.
Queremos isso igual a 4^{m}, logo
k\cdot 4^{m}=4^{m}\quad\Rightarrow\quad k=1.
Portanto uma solução particular é
A_{\text{p}}(m)=m\,4^{m}.

Passo 5

A solução geral da recorrência é soma da homogênea com a particular:
A(m)=A_{\text{h}}(m)+A_{\text{p}}(m)=C\,4^{m}+m\,4^{m}=4^{m}(C+m).
Use a condição inicial A(0)=1 para determinar C. Substituindo m=0:
A(0)=4^{0}(C+0)=C=1.
Assim C=1 e
A(m)=4^{m}(1+m).

Passo 6

Volte para a variável n. Lembre que n=2^{m}, então m=\log_{2}n e 4^{m}=(2^{2})^{m}=2^{2m}=n^{2}. Substituindo:
S(n)=A(m)=4^{m}(1+m)=n^{2}\bigl(1+\log_{2}n\bigr).

Passo 7

Conferência rápida (sanity check): pela árvore de recorrência ou pelo Teorema Mestre temos a=4, b=2, n^{\log_{b}a}=n^{\log_{2}4}=n^{2}. O termo adicional é f(n)=n^{2}, igual ao caso crítico, então a solução assintótica é \Theta(n^{2}\log n). A expressão obtida S(n)=n^{2}(1+\log_{2}n) é consistente com isso (exatamente n^{2}\log_{2}n + n^{2}).

Resposta

S(n)=n^{2}\bigl(1+\log_{2}n\bigr).

Exercícios relacionados