MO417 - Questão para a Prova Oral

Número: 2003-039

Enunciado: Assinale entre as alternativas abaixo a solução para a seguinte recorrência:

T(1) = 0,                     se n = 1;

T(n) = 2T(n - 1) + 1,   se n > 1.

A) O(n lg n);
B) O(n²);
C) O(n³);
D) O(2ⁿ);
E) N.D.A.

Ideia original de: Marcelo Fantinato