MO417 - Questão para a prova oral

Número: 2003-031

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

        /  1, se n = 1;
T(n) = |      
       |          
        \  2 * T(n/2), para n > 1.
               

A solução para esta recorrência é:

A) O( lg n )
B) Θ( n )
C) O( 2^(n/2) )
D) Θ( n lg n )
E) n.d.a.

Ideia original de: Nielsen Cassiano Simões