Prove as seguintes relações envolvendo a notação de Landau:
n^3+4 n^2+2 n+3=O(n^3).

Passo 1

Beleza, o enunciado pede para provar que
n^3 + 4n^2 + 2n + 3 = Ol(n^3r)
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 |f(n)| ;<=; c,|g(n)| é se existirem constantes e tais que, para todo ,
No nosso caso, e .

Passo 3

Agora, vamos comparar termo a termo para achar um n^3 + 4n^2 + 2n + 3 ;<=; n^3 + 4,n^3 + 2,n^3 + 3,n^3 ;=; (1 + 4 + 2 + 3),n^3 ;=; 10,n^3 que funcione. Note que, para :
  • ,
  • ,
  • .
Então:

Passo 4

A partir daí fica fácil: bastou mostrar que, para todo n^3 + 4n^2 + 2n + 3 ;<=; 10,n^3 ,
Logo, podemos escolher e . Isso satisfaz a definição de Big-O.

Resposta

Temos que
n^3 + 4n^2 + 2n + 3 = Ol(n^3r),
com, por exemplo, e .

Exercícios relacionados