Prove as seguintes relações envolvendo a notação de Landau:
.
Passo 1
Resumo do enunciado: a gente quer provar que
Conteúdo da matéria: notação de Landau (Big-O).
O que vamos precisar: a definição de
Passo 2
Definição de Big-O (notação de Landau):
Dizemos que se existem constantes
e
tais que
Dizemos que
Aqui
Passo 3
Vamos encontrar uma desigualdade do tipo
.
Para todo temos
Para todo
Passo 4
Basta escolher
e
.
Então, para todo ,
Então, para todo
Isso mostra exatamente que
Resposta
Portanto, está provado que