MO417 - Questão para a prova oral

Número: 2003-040

Enunciado: A solução para a recorrência

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

é:

A) Θ(n)
B) Θ(log n)
C) Θ(n log n)
D) Θ(n²)
E) n.d.a.

Obs.: considere sqrt(x) como sendo a raiz quadrada de x


Ideia original de: Ricardo Luís Lachi