MO417 - Questão para a prova oral

MO417 - Questão para a prova oral

Número: 2013-007

Enunciado: Dadas as seguintes recorrências, assinale a alternativa correta:

T₁(n) = 5T(n/6) + n²
T₂(n) = 5T(n/2) + n^{lg 5}
T₃(n) = 5T(n/2) + n²

a. T₁(n) possui uma ordem de crescimento maior do que T₂(n)
b. T₂(n) possui uma ordem de crescimento maior do que T₃(n)
c. T₃(n) = Θ(n^{lg 5} lg n)
d. T₁(n) = Θ(n^{log₆ 5})
e. NDA

Ideia original de: Anderson Coelho Weller