1. Qual a solução de relação de recorrência T(2 n)=T(n)+n ?

Passo 1

O enunciado pede para resolver a relação de recorrência
T(2n)=T(n)+n
para n da forma n=2^k. O conteúdo é solução de recorrência com variação de argumento por fator constante (doubling). Para resolver, vamos usar mudança de variável para um índice k.

Passo 2

Defina n=2^k e
S(k)=T\bigl(2^k\bigr).
Então, quando n passa para 2n, isto é, de 2^k para 2^{k+1}, a recorrência vira
S(k+1)=T\bigl(2^{k+1}\bigr)=T\bigl(2\cdot 2^k\bigr)=T(2n)=T(n)+n=S(k)+2^k.

Passo 3

Temos agora a nova recorrência
S(k+1)=S(k)+2^k,
com condição inicial S(0)=T(2^0)=T(1). Para encontrar S(k), desdobramos a soma:

Passo 4

Unrolando de 0 a k-1,
S(k)=S(0)+\sum_{i=0}^{k-1}2^i =T(1)+\bigl(2^k-1\bigr) =T(1)-1+2^k.

Passo 5

Voltando à variável original, como 2^k=n, obtemos
T(n)=S(k)=T(1)-1+n.
Em termos de ordem de grandeza, isso significa T(n)=\Theta(n).

Resposta

T(n)=n + T(1) - 1, ou simplesmente T(n)=\Theta(n).

Exercícios relacionados