Question

O cálculo de complexidade é parte essencial do projeto e da análise de algoritmos. Uma ferramenta chave usada nesta atividade é a notação Theta (Θ). Ela oferece uma maneira objetiva de descrever o comportamento assintótico de algoritmos e possibilita a comparação da eficiência entre eles.



Considerando as funções T1(n) = log2n + n e T2(n) = n, analise as asserções a seguir e a relação proposta entre elas.



I. Um algoritmo A2 com uma complexidade T2 tem uma eficiência computacional melhor que um algoritmo A1 com complexidade T1.

Porque:

II. A função T1 tem limite assintótico dado por T1(n) = Θ(T2(n)).



A seguir, assinale a alternativa correta.





As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.





As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.





A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.





A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.





As asserções I e II são proposições falsas.

Answer 1

Resposta:

A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.

Explicação:

É preciso observar que n = O(log2n + n). Adicionalmente, temos que verificar se log2n + n = O(n), ou seja, log2n + n ≤ cn, c > 0. Como log2n ≤ n (pois n ≤ 2n), temos que log2n + n ≤ 2n, tomando c = 2 e n ≥ 1. Portanto, T1(n) = Θ(T2(n)).