MO417 - Questão para a prova oral

Número: 2013-014

Enunciado : Qual a ordem de crescimento das soluções para a recorrência abaixo:  

T( n ) = T( n^1/2 ) + n

Como sempre, supõem-se valores constantes para n pequeno e arrendondamento da raiz para cima ou para baixo.

a)      Θ ( n )

b)      Θ ( n² )

c)      Θ ( n log log n )

d)     Θ ( n log n )

e)      N.D.A. 

Ideia original de:  Erick Aguiar Donato