Usando o teorema mestre, assinale a alternativa contendo a ord...

(C) Q(n^3)

Explicação passo-a-passo:

Consideremos T(n) = 8*T(n/2) + n^2, para n maior que 1  e S(1) = q, para n = 1, onde q é uma constante positiva.

Segundo o Teorema Mestre, temos que S(n) = a*S(n/b) + n^c, para:

(1) "n" deve ser maior que ou igual a 2;

(2) n = b^m;

(3) "a" deve ser maior que ou igual a 1;

(4) "b" deve ser maior que 1;

(5) "c" deve ser um número real não negativo.

(6) S(1) deve ser maior que ou igual a zero.

Comparando as duas recorrências, temos que:

(1) n é maior que 1;

(2) n = 2^m;

(3) a = 8;

(4) b = 2;

(5) c = 2;

(6) Como q = 8, T(1) é maior que ou igual a zero.

Como todas as condições são satisfeitas, verificamos que:

3. a > b^c. ( pois 8 > 2^2 )

Assim, S(n) = Q(n^(log de "a" na base "b"))

Voltando à recorrência T(n), temos que:

T(n) = Q(n^(log de 8 na base 2) = Q(n^3).

Note que log de 8 na base 2 = x.

2^x = 8 2^x = 2^3 x = 3