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

Passo 1

Resumo do enunciado: a gente quer provar que
3n^2 - 4n = O(n^2)
Conteúdo da matéria: notação de Landau (Big-O).
O que vamos precisar: a definição de f(n)=O(g(n)) e encontrar constantes C>0 e n0 tais que, para todo n>= n0, valha
|f(n)| <= C,|g(n)|

Passo 2

Definição de Big-O (notação de Landau):
Dizemos que f(n)=O(g(n)) se existem constantes C>0 e n0inN tais que
forall,n>= n0: |f(n)| <= C,|g(n)|
Aqui f(n)=3n^2-4n e g(n)=n^2.

Passo 3

Vamos encontrar uma desigualdade do tipo |3n^2-4n|<= C,n^2.
Para todo n>=1 temos
|3n^2-4n|;=;3n^2 + 4n ;<=;3n^2 + 4n^2 ;=;7n^2

Passo 4

Basta escolher C=7 e n0=1.
Então, para todo n>= n0,
|3n^2-4n|<= 7,n^2
Isso mostra exatamente que 3n^2-4n=O(n^2).

Resposta

Portanto, está provado que
3n^2 - 4n = O(n^2)

Exercícios relacionados