Dado o algoritmo recursivo abaixo para valores de n maiores ou iguais a zero, assinale a alternativa que melhor define a equação de recorrência.

A resposta correta é: “T(n) =T(n - 1) + T(n – 2) + Θ(1) para n > 1 e T(n) = Θ(1) caso contrário. ” Justificativa: Caso n seja 0 ou 1, temos uma instrução constante, então T(n) = Θ(1). Caso n seja maior que 1, são realizadas duas chamadas recursivas com n – 1 e n – 2 elementos, respectivamente, o que leva a T(n) = T(n - 1) + T(n – 2) + Θ(1).