Semana: 03/03/2003 a 07/03/2003
Assunto: Recorrências

Seja a seguinte função de recorrência:

T(n) = 1, se n =1

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

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

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

Autor: Augusto Jun Devegili
RA: 25620