MO417 - Questão para a prova oral

Número: 2013-016

Enunciado: Suponha que a função f satisfaz a relação de recorrência

f(n) = 2 f(n^1/2) + 1.

Dê uma estimativa assintótica correta da função f(n).

(a) Θ(log n)
(b) Θ(n)
(c) Θ(n log n)
(d) Θ(n²)
(e) NDA

Ideia original de: Marcelo Palma Salas