a) Defina o fato de que
é
, em que
e
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
é
diretamente para demonstrar ou negar que
é
.
c) Use a definição do fato de que
é
diretamente para demonstrar ou negar que
é
.
b) Use a definição do fato de que
c) Use a definição do fato de que
Passo 1
O enunciado trata da notação assintótica “
” (big-O), que é usada para comparar o crescimento de duas funções inteiras
e
. A definição que vamos usar é a seguinte:
“Dizemos que é
se existirem constantes
e
tais que, para todo
, vale
“Dizemos que
Nos passos seguintes, aplicamos essa definição diretamente aos polinômios dados.”
Passo 2
Queremos mostrar que
Para
temos as desigualdades elementares
Somando-as:
Logo, basta escolher
e
. Então, para todo
,
o que prova que
é
.
Passo 3
Agora verificamos se
Suponha, por contradição, que existam
e
tais que, para todo
,
Então
Porém, ao fazer
, o quociente
vai a
. Logo, para
suficientemente grande, ele excede qualquer constante
. Isso contradiz a existência de constantes que satisfaçam a definição. Portanto
não é
.
Resposta
a) Dizemos que
é
se existirem constantes
e
tais que, para todo
, valha
b)
é
(por exemplo, com
e
).
c)
não é
.