[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 dá a afirmação
Lista do que foi dado e do que se pede:
- Função a comparar:
. - Função de referência:
. - Pergunta: a afirmação é verdadeira ou falsa? Ou seja, existe constante
e tais que, para todo ,
Passo 2
Definição de
(Big‑O), explicada devagarinho: dizemos que
se existem constantes
e
tais que, para todo
,
Aqui
e
são funções não negativas para
suficientemente grande;
é um multiplicador constante e
é o ponto a partir do qual a desigualdade vale sempre. Nosso objetivo é achar tais
e
(ou provar que não existem).
Passo 3
Uma desigualdade útil sobre logaritmos que usamos com frequência: para
vale
Pequena justificativa: considere
. Então
para
, logo
é crescente em
e
, portanto
para
, o que dá
.
Passo 4
Multiplicando a desigualdade do passo anterior por
(que é não negativo para
), obtemos, para
,
Ou seja, para todo
temos
Portanto podemos escolher as constantes
e
, que satisfazem exatamente a condição da definição de Big‑O.
Passo 5
Resumo do raciocínio: encontramos
e
tais que, para todo
,
. Isso cumpre a definição de
.
Resposta
Verdadeira