Prove as seguintes relações envolvendo a notação de Landau:
Qualquer polinômio em
de grau
é
.
Qualquer polinômio em
Passo 1
Beleza, o enunciado quer que a gente prove que qualquer polinômio em
de grau
é
.
Conteúdo envolvido: notação de Landau (Big-O) e algumas desigualdades básicas para polinômios.
O que a gente vai precisar:
Conteúdo envolvido: notação de Landau (Big-O) e algumas desigualdades básicas para polinômios.
O que a gente vai precisar:
- A definição de
, ou seja, existem constantes e tais que, para todo , vale
2) A propriedade de que, se
3) Desigualdade triangular para somas de termos absolutos.
Passo 2
Vamos escrever um polinômio genérico de grau
em
:
onde cada
Passo 3
Aplicando valor absoluto e a desigualdade triangular, a gente tem:
$$|p(n)| ;=;\bigl|a_k n^k + a_{k-1} n^{k-1} + \cdots + a_0\bigr|
;\le; |a_k|,|n^k| + |a_{k-1}|,|n^{k-1}| + \cdots + |a_0|,. $$
Passo 4
Agora, como
, para cada expoente
vale
. Então
Substituindo na soma,
$$|p(n)| ;\le; |a_k|,n^k + |a_{k-1}|,n^k + \cdots + |a_0|,n^k
;=;\Bigl(|a_k| + |a_{k-1}| + \cdots + |a_0|\Bigr),n^k,. $$
Passo 5
Seja
Então, para todo
que é exatamente a definição de
.
Resposta
Portanto, mostramos que qualquer polinômio de grau
satisfaz