Prove as seguintes relações envolvendo a notação de Landau:
.
Passo 1
Beleza, o enunciado pede para provar que
Isso é um exercício de notação de Landau (ou Big-O), que a gente usa para mostrar que uma função cresce no máximo na mesma ordem de outra, ignorando constantes e termos de grau menor. Para resolver, vamos precisar da definição de
e de umas manhas básicas para comparar potências de
.
Passo 2
Primeiro, lembra da definição:
Uma função é
se existirem constantes
e
tais que, para todo
,
Uma função
No nosso caso,
e
.
Passo 3
Agora, vamos comparar termo a termo para achar um
que funcione. Note que, para
:
-
, -
, -
.
Então:
Passo 4
A partir daí fica fácil: bastou mostrar que, para todo
,
Logo, podemos escolher
e
. Isso satisfaz a definição de Big-O.
Resposta
Temos que
com, por exemplo,
e
.