MO417 - Questão para a prova oral

Número: 004

Enunciado:

Considere os seguintes tempos de execução para um conjunto de algoritmos quaisquer:

i) T(n) = 5n³ + 40n - 1/n²

ii) T(n) = (n² + 2n - 15)/(n - 3)

iii) T(n) = 256

iv) T(n) = lg 2ⁿ + 300n

É correto afirmar que em notação Θ os tempos de execução são, respectivamente:

1. Θ(n^-1/2), Θ(n²), Θ(256), Θ(n lg n)
2. Θ(n²), Θ(n²), Θ(256), Θ(2ⁿ)
3. Θ(n³), Θ(n), Θ(1), Θ(n)
4. Θ(n³), Θ(n), Θ(1), Θ(lg n)
5. NDA

Autor: Ewerton Almeida Silva