MO417 - QUESTÃO PARA PROVAL ORAL

Número:

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