Mostre que
é
e
é
.
Passo 1
O enunciado pede para mostrar duas relações de ordem de crescimento (“big-O”):
-
. -
.
Para isso vamos usar a definição: dizemosse existem constantes e tais que, para todo ,
Passo 2
Mostrando
.
Para temos
Para
Mas
. Logo, para todo
,
Isso prova a primeira relação com
e
.
Passo 3
Mostrando
.
Para qualquer vale
Para qualquer
Assim
Portanto, para todo
,
Isto mostra a segunda relação com
e
.
Resposta
Mostramos que
e