Prove as seguintes relações envolvendo a notação de Landau:
Qualquer polinômio em n de grau k é O(n^k).

Passo 1

Beleza, o enunciado quer que a gente prove que qualquer polinômio em n de grau k é Ol(n^kr).
Conteúdo envolvido: notação de Landau (Big-O) e algumas desigualdades básicas para polinômios.
O que a gente vai precisar:
  1. A definição de f(n)=O(g(n)), ou seja, existem constantes c>0 e n0 tais que, para todo n>= n0, vale
|f(n)|<= c,|g(n)|,
2) A propriedade de que, se 0<= i<= k e n>=1, então n^i<= n^k.
3) Desigualdade triangular para somas de termos absolutos.

Passo 2

Vamos escrever um polinômio genérico de grau k em n:
p(n)=ak n^k + ak-1 n^k-1 + cdots + a1 n + a0,,
onde cada ai é uma constante real (ou complexa, mas a ideia é a mesma).

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 n>=1, para cada expoente i<= k vale n^i<= n^k. Então
|ai|,n^i <= |ai|,n^kpara todo i=0,1,dots,k
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
c = |ak| + |ak-1| + cdots + |a0|,, n0 = 1,
Então, para todo n>= n0=1, a gente garantiu
|p(n)| <= c,n^k,,
que é exatamente a definição de p(n)=O(n^k).

Resposta

Portanto, mostramos que qualquer polinômio de grau k satisfaz
p(n)=Ol(n^kr),

Exercícios relacionados