Question

Usando o teorema mestre, assinale a alternativa contendo a ordem de grandeza para a relação de recorrência abaixo.
T(n)=8T(n/2)+n para n>1
T(1)=q para n=1, onde q é uma constante positiva.

Answer 1

Resposta:

(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

Answer 2

A ordem de grandeza será de: (C) Q(n^3)

Tomando T(n) = 8*T(n/2) + n^2, quando:

n> 1  e S(1) = q,

n = 1,

q é constante positiva.

Considerando o Teorema Mestre, segundo o qual:  S(n) = a*S(n/b) + n^c

n≥  2;

n = b^m

a≥ 1;

b> 1;

c é número real não negativo.

S(1) ≥ 0.

Quando fazemos uma comparação, temos que:

n > 1;

n = 2^m;

a = 8;

b = 2;

c = 2;

Quando q = 8, T(1) ≥ 0

Verificação:

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

S(n) = Q(n^(ᵃ㏒ₙ)

usando T(n), temos que:

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

T(n)= Q(n^3)

2^x = 8

2^x = 2^3

x = 3