MO417 - Questão para a prova oral

Número:

Enunciado: Considere as seguintes recorrências:

T1(n) = 1, n = 1

        = T1(n/2) + n, n > 1

T2(n) = 1, n = 1

        = T2(n/2) + n^2, n > 1

T3(n) = 1, n = 1

        = T3(n/2) + n^3, n > 1

Com relação às ordens de crescimento das funções, é correto afirmar que: 

A) T2(n) > T3(n) > T1(n)

B) T2(n) > T1(n) > T3(n)

C) T3(n) > T2(n) > T1(n)

D) T3(n) > T1(n) > T2(n)

E) N.D.A

Ideia original de: Thaís Harumi Ussami