Questão para a prova oral (Semana 3: Recorrências)

Enunciado:
Com relação às recorrências, assinale a alternativa INCORRETA:

A) A resolução de recorrências através do método da substituição é baseada em duas etapas: (1) pressupor a forma da solução. (2) usar a indução matemática para encontrar as constantes e mostrar que a solução funciona.
B) A troca de variáveis é uma manipulação algébrica utilizada para tornar uma recorrência "desconhecida" em uma mais simplificada, e portanto "conhecida".
C) A análise do algoritmo de ordenação mergesort resulta na recorrência: T(n) = 2T(n/2) + O(n), que não pode ser resolvida pelo método mestre.
D) As árvores de recursão são extremamente úteis quando a recorrência descreve o tempo de execução de um algoritmo de dividir e conquistar.
E) NDA.

Autor(a): Eduardo Akira Yonekura