MO417 - Questão para a Prova Oral

Número: 2003-035

Enunciado: Considere a seguinte equação de recorrência:

   T(n) = 1, se n ≤ 2
   T(n) = 2T(sqrt(n)) + lg n, se n > 2

É correto afirmar que esta recorrência tem solução:

a) impossível de ser resolvida
b) O(lg n lg lg n)
c) Θ(n lg n)
d) O(lg lg n)
e) NDA


Ideia original de: Augusto Jun Devegili