[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 pede que eu diga se a afirmação abaixo é verdadeira ou falsa, usando notação assintótica:
Informações dadas: a expressão
e o conjunto assintótico
. A pergunta é: a função
pertence à classe
com
?
Passo 2
Vou lembrar a definição de
(Big-O) — isso é essencial para provar se a afirmação é verdadeira. A definição formal é:
Explicando com calma: escolhemos uma constante positiva
e um ponto
a partir do qual, para todo
maior ou igual a
, o valor de
fica no máximo igual a
vezes
. Na prova de exame, o truque é reescrever
em função de
e encontrar
e
explicitamente.
Passo 3
Vou reescrever a função dada de forma a relacioná‑la com
. Observe que potências com soma no expoente se comportam assim:
Essa igualdade é só a propriedade básica
.
Passo 4
Calculo o valor numérico de
para ter a constante explícita:
Portanto, da etapa anterior temos a forma
Passo 5
Agora aplico a definição de
. Queremos
e
tais que, para todo
,
Usando a igualdade da etapa anterior, isso fica
Como
para todo
, podemos dividir ambos os lados por
sem mudar a desigualdade, obtendo
Logo basta escolher qualquer constante
maior ou igual a
. Para
podemos escolher
(ou
); a desigualdade já vale para todo
porque a expressão é exatamente igual a
.
Passo 6
Escolhendo explicitamente
e
, temos que para todo
:
portanto a condição da definição de
é satisfeita. Isso é uma prova direta e formal, do jeitinho que pedem na prova.
Passo 7
Interpretação e dica prática: quando uma função é apenas uma constante multiplicativa de outra (aqui
), então
. Em geral, para qualquer base fixa
e qualquer inteiro constante
, vale
Na prova, basta expor a igualdade, calcular a constante
e declarar
e um
qualquer.
Resposta
Verdadeira.