MO417 - Questão para a prova oral

Número: 2009-024

Enunciado: Considere a seguinte recorrência:

 T(n) = 5   para n ≤ 3
 T(n) = 3T(piso(n/4)) + n para n ≥ 4
 

Podemos dizer que T(n) tem ordem de crescimento:

1. Θ(n)
2. Θ(nlg(n))
3. Θ(n²)
4. Θ(n³)
5. NDA

Ideia original de: Jonathas Campi Costa