Considere a relação de recorrência dada por S open parentheses n close parentheses equals 3 S open parentheses n over 2 close parentheses plus n sq...

Vamos analisar cada alternativa: a. S(n) = Θ(n²): Incorreta, pois a relação de recorrência não indica um crescimento quadrático. b. S(n) = Θ(n³): Incorreta, pois a relação de recorrência não indica um crescimento cúbico. c. S(n) = Θ(n^(log₂3)): Incorreta, pois a relação de recorrência não se encaixa nesse padrão. d. S(n) = Θ(n³ log n): Incorreta, pois a relação de recorrência não indica um crescimento cúbico logarítmico. e. S(n) = Θ(n² log n): Correta, pois a relação de recorrência sugere um crescimento quadrático logarítmico. Portanto, a alternativa correta é: e) S(n) = Θ(n² log n).

Resposta:

Explicação passo a passo:

Para encontrar a ordem de grandeza da relação de recorrência , vamos usar o Método Mestre, que é uma maneira comum de analisar recorrências desse tipo.

O Método Mestre tem três casos que permitem calcular a complexidade assintótica para uma recorrência geral da forma:

Com , precisamos calcular . Como  e , temos . Assim, .

Em seguida, comparamos :

1. Caso 1

Ocorre quando . Este caso resulta em uma complexidade de .

2. Caso 2

Ocorre quando , e a complexidade é .

3. Caso 3

Ocorre quando , onde . Nesse caso, a complexidade é dada por .

Como , estamos no Caso 1, porque  é maior que , mas menor do que . Portanto, a complexidade é .

Em resumo, para , a alternativa correta em termos de ordem de grandeza é .