[1 pt] Para cada afirmação abaixo, informe se ela é verdadeira ou falsa. Use a notação assintótica para desenvolver e justificar a sua resposta.
Passo 1
O enunciado apresenta a afirmação
e pede que eu informe se essa afirmação é verdadeira ou falsa, usando notação assintótica e justificando a resposta.
Informações dadas: a expressão e a comparação com
. Não há outras condições explícitas, então entendemos
como variável que tende a infinito (ou
,
).
Informações dadas: a expressão
Passo 2
Vou recordar a definição de
(Big‑O) de forma clara e simples. Dizemos que uma função
é
se existem constantes positivas
e
tais que, para todo
,
Aqui
é uma constante que “amortece” a diferença de escala entre
e
, e
é a partir de que ponto essa desigualdade passa a valer para todos os
maiores. Em linguagem informal:
cresce no máximo tão rápido quanto
, até uma constante multiplicativa, para
grandes.
Passo 3
Escrevo a função em forma polinomial para ficar mais claro o termo dominante:
Ou seja,
.
Passo 4
Agora vou encontrar uma desigualdade do tipo
válida para
grandes. Para
valem as desigualdades simples
pois multiplicar por
preserva/desloca para cima. Usando essas relações, tenho para
:
E, como
para
, segue
Compondo as desigualdades obtemos, para todo
,
Passo 5
A desigualdade do passo anterior mostra que podemos escolher
e
e satisfazemos a definição de Big‑O:
Portanto
.
Passo 6
Como eu acabei de provar que
(exibindo
e
), a afirmação dada no enunciado, que nega essa relação, não é correta. Para reforçar a intuição, uma verificação alternativa é calcular o limite do quociente:
o que também indica que o quociente é limitado (na verdade tende a
), logo
.
Resposta
Falso.