Análise de Algoritmos

Exercício 1.
Encontre a solução fechada para a sequência T definida por:
T(1) = 7
T(n) = 2T(n-1)+1, onde n ≥ 2
Resposta:
primeiro tem que expandir:
K = 1 : T(n) = 2T(n-1) + 1
K = 2 : T(n) = 2[2T(n - 2) + 1]+1 = 4T(n - 2) + 3
K = 3 : T(n) = 4[2T(n - 3) + 1]+3 = 8T(n - 3) + 7

Segundo: conjecturar, após a expansão, T(n) = 2^nT(n - k) + 2^n – 1 a expansão irá parar quando k = n – 1.
T(n) = 2^(n-1)T(n – (n - 1)) + 2^(n-1)-1
T(n) = 2^(n-1)*7+ 2^(n-1)-1=8* 2^(n-1)-1
T(n) = 2^(3 )* 2^(n-1)-1= 2^(n-2)-1
Terceiro: hipótese Indutiva: T(n) = 2^(n-2) – 1 ; T(n) = 2^3-1 = 7
Agora temos que demonstrar que T(n - 1) = 2^(n-3)-1
T(n + 1) = 2T(n + 1 - 1) + 1
T(n + 1) = 2T(n) + 1
T(n + 1) = 2T(2^(n+2)-1) + 1
T(n + 1) = 2^(n+3)-1
A fórmula fechada é 2^(n+2)-1

Exercício 2
Encontre uma recorrência que expresse a sequencia: 1, 5, 7, 53, 161...
Resposta:
T(1) = 1
T(n) = 2 + 3T(n – 1), para n ≥ 2

Exercício 3
Escreva uma fórmula de recorrência para cada uma das sequencias abaixo e identifique se a fórmula encontrada é fechada ou não. 1, 3, 5, 7, 9...
Resposta:
T(1) = 1
T(n) = T(n -1) + 2, para n > 2

1, 4, 9, 16, 25...
Resposta:
n^2, para n ≥ 1

1, 3, 7, 15, 31, 63...
Resposta:
T(1) = 1
T(n) = 2T(n - 1) + 1, para 2 ≤ n ≤ 6