Árvores de recursão podem ser empregadas para a obtenção de soluções assintoticamente justas para recorrências. Esses limites são expressos por mei...

Árvores de recursão podem ser empregadas para a obtenção de soluções assintoticamente justas para recorrências. Esses limites são expressos por meio da notação Theta e oferecem um poderoso recurso para a análise do desempenho de a

Considerando essas informações e o conteúdo estudado, analise a sequência de números a seguir S = ( 1, 2, 22, 23, ..., 2n, …) e assinale a alternativa que apresenta a recorrência correta para S.

T(n) = 2 × T(n – 1), se n ≥ 1 e T(n) = 1, se n = 0.
(Resposta correta. Todos os elementos de S são potências de 2. Logo, o termo geral da sequência é 2n e o caso geral da recorrência precisa envolver uma potência desse tipo, ou seja, T(n – 1) x 2. Além disso, é preciso definir o caso base da relação. Como o primeiro elemento de S é 1, o caso base pode ser expresso como T(0) = 1. Portanto, para n = 4, a sequência de S seria obtida como:
T(4) = 2 × T(3)
T(3) = 2 × T(2)
T(2) = 2 × T(1)
T(1) = 2 × T(0)
T(0) = 1
Logo, S = ( T(0), 2 × T(1), 2 × T(2), 2 × T(3), 2 × T(4) ) = (1, 2, 4, 8, 16) = (1, 21, 22, 23, 24) para n = 4.)


a) T(n) = 2 × T(n – 1), se n ≥ 1 e T(n) = 1, se n = 1.
b) T(n) = 2 × T(n – 1), se n ≥ 1 e T(n) = 1, se n = 0.
c) T(n) = 2 × T(n – 1), se n ≥ 0 e T(n) = 1, se n = 1.
d) T(n) = 2 × T(n – 1), se n ≥ 0 e T(n) = 1, se n = 0.
e) T(n) = 2 × T(n – 2), se n ≥ 2 e T(n) = 1, se n = 0 ou n = 1.