Assunto: Recorrência
Enunciado
Sobre o estudo de recorrências NÃO podemos afirmar:
A) O método mestre não é aplicável para todas as recorrências do tipo T(n) = a T(n/b) + f(n).
B) Durante a prova da solução da recorrência no método de substituição, deve-se sempre chegar a forma exata da hipótese para garatir que o resultado é válido.
C) Usando o método mestre para T(n) = T(n/3) + T(2n/3) + 3n, chega-se a O(n lg n).
D) Uma recorrência como T(n) = T(n/3 + 9) + n2, em geral, pode ser simplificada para T(n) = T(n/3) + n2 pois (n/3) se aproxima de (n/3) + 9 para valores de n suficientemente grandes.
E) N.D.A.