MO417 - Questão para a prova oral

Número: 2010-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³), Θ(n²), Θ(256), Θ(lg n)
2. Θ(n³), Θ(n²), Θ(256), Θ(n)
3. Θ(n³), Θ(n), Θ(1), Θ(n)
4. Θ(n³), Θ(n), Θ(1), Θ(lg n)
5. NDA

Ideia original de: Ewerton Almeida Silva