Seu próximo nível começa aqui
Seu desenvolvimento não pode ter limites. Garanta sua Assinatura Ilimitada e libere uma preparação completa com os melhores professores do Brasil.
Acerca do Teorema mestre, sejam a ≥ 1 e b > 1...
Acerca do Teorema mestre, sejam a ≥ 1 e b > 1 constantes, seja f(n) uma função e seja T(n) definida no domínio dos números inteiros não negativos pela recorrência
T(n) = aT(n/b) + f(n),
onde interpretamos que n/b significa n/b ou n/b. Então, T(n) tem os seguintes limites assintóticos:
I. Se f(n) = O(nlogb a-) para alguma constante > 0, então T(n) = Θ(nlog b a).
II. Se f(n) = Θ(nlogb a), então T(n) = Θ(nlogb a lg n).
III. Se f(n) = (nlogb a+) para alguma constante >0, e se af(n/b) ≤ cf(n) para alguma constante c < 1 e todos os n suficientemente grandes, então T(n) = Θ(f(n)).
Nesse sentido, assinale a alternativa CORRETA.
A
No caso I, se a função nlogba a for a maior, então a solução é T(n) = Θ(nlogba).
B
No caso III, se a função f(n) for a maior, então a solução é T(n) = Θ(f(n/b)).
C
No caso II, se as duas funções tiverem o mesmo tamanho, multiplicamos por um fator logarítmico e a solução é T(n) = Θ (nlogba lg n) = Θ( nlogf(n) lg n).
D
No caso I, f(n) não só tem de ser menor que nlogba, mas deve ser polinomialmente maior. Isto é, f(n) deve ser assintoticamente menor que nlogba por um fator n para alguma constante >0.
E
No caso III, f(n) não apenas deve ser maior que nlogba, ela tem de ser polinomialmente maior e, além disso, satisfazer à condição de "regularidade" expressa por af (n/b) ≥ cf (n).