Exercícios resolvidos - Complexidade assintótica

Utilizando as definições para as notações assintóticas, prove se são verdadeiras ou falsas as seguintes afirmativas:
1) 3n³ + 2n² + n + 1 = O(n³)
3n³ + 2n² + n + 1 <= c * n³
3 + 2/n + 1/n² + 1 <= c
menor valor possível de c: 3 + 2 + 1 + 1 = 7
verdadeira para c = 7 e n0 = 1

2) 7n² = O(n)
7n² <= c * n
7n <= c
não existe um valor para c que seja sempre maior que n, portanto a afirmação é falsa

3) 2ⁿ⁺² = O(2ⁿ)
2ⁿ⁺² <= c * 2ⁿ
2ⁿ  * 2²<= c * 2ⁿ
2² <= c
verdadeira para n0 = 1 e c = 4

4)2²ⁿ = O(2ⁿ)
(2ⁿ)² <= c * 2ⁿ
2ⁿ <= cnão existe um valor para c que seja sempre maior que n, portanto a afirmação é falsa

5) 5n² + 7n = Θ(n²)
5n² + 7n <= c2 * n²             c1 * n² <= 5n² + 7n
5 + 7/n <= c2                     c1 <= 5 + 7/n
5 + 7/1 <= c2                     c1 <= 5 + 7/infinito
verdadeiro para n0 = 1, c1 = 5 e c2 = 12
no cálculo de c1, considera-se n0 tendendo ao infinito fazendo 7/n assumir o menor valor possível; já no cálculo de c2, considera-se n0 = 1 para que 7/n assuma o maior valor possível.

6) 6n³ + 5n² ≠ Θ(n²)
c1 * n² <= 6n³ + 5n²           6n³ + 5n² <= c2 * n²
c1 <= 6n + 5                      6n + 5 <= c2
para n0 = 1, c1 pode valer 11. Porém, não existe um valor fixo para c2. Portanto, a afirmativa é VERDADEIRA, pois perguntava se a expressão era DIFERENTE de Θ(n²).

7) 9n³ + 3n = Ω(n)
9n³ + 3n >= c * n
9n² + 3 >= c
verdadeira para n0 = 1 e c = 12.

Obs: nem sempre n0 precisa ser 1. Vários pares (ou triplas) de valores podem resolver as expressões.