a) Defina o fato de que f(n) é O(g(n)), em que f(n) e g(n) são funções do conjunto dos números inteiros positivos para o conjunto dos números reais.
b) Use a definição do fato de que f(n) é O(g(n)) diretamente para demonstrar ou negar que n^{2}+18 n+107 é O\left(n^{3}\right).
c) Use a definição do fato de que f(n) é O(g(n)) diretamente para demonstrar ou negar que n^{3} é O\left(n^{2}+18 n+107\right).

Passo 1

O enunciado trata da notação assintótica “ O” (big-O), que é usada para comparar o crescimento de duas funções inteiras f(n) e g(n). A definição que vamos usar é a seguinte:
“Dizemos que f(n) é O(g(n)) se existirem constantes C>0 e n_{0}\in\mathbb{N} tais que, para todo n\ge n_{0}, vale
|f(n)| \le C\,|g(n)|\,.
Nos passos seguintes, aplicamos essa definição diretamente aos polinômios dados.”

Passo 2

Queremos mostrar que
f(n)=n^{2}+18n+107 \quad\text{é}\quad O\bigl(n^{3}\bigr).é
Para n\ge1 temos as desigualdades elementares
n^{2}\le n^{3},\quad 18n\le 18\,n^{3},\quad 107\le 107\,n^{3}.
Somando-as:
n^{2}+18n+107 \le n^{3} + 18\,n^{3} + 107\,n^{3} = 126\,n^{3}.
Logo, basta escolher C=126 e n_{0}=1. Então, para todo n\ge n_{0},
n^{2}+18n+107 \le 126\,n^{3},
o que prova que n^{2}+18n+107 é O(n^{3}).

Passo 3

Agora verificamos se
g(n)=n^{3} \quad\text{é}\quad O\bigl(n^{2}+18n+107\bigr).é
Suponha, por contradição, que existam C>0 e n_{0} tais que, para todo n\ge n_{0},
n^{3} \le C\,\bigl(n^{2}+18n+107\bigr).
Então
\frac{n^{3}}{n^{2}+18n+107} \le C.
Porém, ao fazer n\to\infty, o quociente
\frac{n^{3}}{n^{2}+18n+107} =\frac{n}{1+\tfrac{18}{n}+\tfrac{107}{n^{2}}}
vai a +\infty. Logo, para n suficientemente grande, ele excede qualquer constante C. Isso contradiz a existência de constantes que satisfaçam a definição. Portanto n^{3} não é O(n^{2}+18n+107).

Resposta

a) Dizemos que f(n) é O(g(n)) se existirem constantes C>0 e n_{0} tais que, para todo n\ge n_{0}, valha
|f(n)| \le C\,|g(n)|.
b) n^{2}+18n+107 é O(n^{3}) (por exemplo, com C=126 e n_{0}=1).
c) n^{3} não é O(n^{2}+18n+107).

Exercícios de Livros Relacionados