MO417 - Questão para a prova oral

MO417 - Questão para a prova oral

Número: 2013-015

Enunciado: Sejam a ≥ 1 e b > 1 constantes, seja f(n) uma função e T(n) definida sobre os números inteiros não negativos pela recorrência

T(n) = aT(n/b) + f(n)

É INCORRETO  afirmar que: 

1. Se a = b e f(n) = n então T(n) = Θ(n lg n)
2. Se a = b² e f(n) = n então T(n) = Θ(n²)
3. Se a = b e f(n) = n²  então T(n) = Θ(n²)
4. Se a = b²  e f(n) = n² então T(n) = Θ(n lg n) 
5. NDA

Ideia original de: Anderson Carlos Sousa e Santos