Considere as funções
e
. Podemos afirmar que
?
Passo 1
O enunciado dá as funções
e
e pergunta se
O conteúdo aqui é a notação de Landau (Big-O). Vamos usar a definição: dizer que
significa que existem constantes
e
tais que, para todo
,
Passo 2
Escrevemos
Passo 3
Precisamos mostrar que, para
grande, esse somatório fica abaixo de uma constante vezes
. Note que, para
, vale
Passo 4
Além disso, para
temos
e
. Assim, para todo
,
Logo, basta escolher
e
para satisfazer a definição de Big-O.
Resposta
Sim. De fato,
.\n