Mostre que
é
.
Passo 1
O enunciado pede para mostrar que a função
definida por
é
quando
. Vamos usar a definição formal de Big-O: existem constantes
e
tais que
Passo 2
Para
temos
. Assim,
Passo 3
Continuando a estimativa,
Para
segue
Passo 4
Basta escolher
e
. Então para todo
vale
o que, pela definição, mostra que
é
.