Question

Considere a relação de recorrência dada por S abre parênteses n fecha parênteses igual a 3 S abre parênteses n sobre 2 fecha parênteses mais n ao quadrado vírgula espaço p a r a espaço n maior ou igual a 2 vírgula espaço n igual a 2 à potência de m.

Assinale a alternativa correta, com respeito à ordem de grandeza de S(n)
a.

S left parenthesis n right parenthesis equals capital theta left parenthesis n to the power of log subscript 2 3 end exponent right parenthesis.
b.

S left parenthesis n right parenthesis equals capital theta left parenthesis n cubed log n right parenthesis.
c.

S left parenthesis n right parenthesis equals capital theta left parenthesis n cubed right parenthesis.
d.

S left parenthesis n right parenthesis equals capital theta left parenthesis n squared log n right parenthesis.
e.

S left parenthesis n right parenthesis equals capital theta left parenthesis n squared right parenthesis.

Answer 1

Resposta:

Alternativa S(n) = θ(n²)

Explicação passo a passo:

AVA

Answer 2

Resposta:

S(n) = Θ(n^2)

Explicação passo a passo:

Segundo o TEOREMA MESTRE se cumpre:

S(n)=aS(n/b)+nc

em que n = bm, a e b são inteiros, a ≥ 1, b > 1 e

c é um número real não negativo. Então

Se a < bc ⇒ S(n)= Θ(nc)

Se a = bc ⇒ S(n)= Θ(nclogn)

Se a > bc ⇒ S(n)= Θ(nlogba)

Substituindo a= 3, b=2, c= 2 verificamos que estamos no Primeiro Caso:

S(n)= Θ(n^2)