Considere as funções f(n)=3 n^{2}-n+4 e g(n)=n \log n+5. Podemos afirmar que f(n)+g(n)=O\left(n^{2}\right) ?

Passo 1

O enunciado dá as funções
f(n)=3n^{2}-n+4
e
g(n)=n\log n+5
e pergunta se
f(n)+g(n)=O(n^{2}).
O conteúdo aqui é a notação de Landau (Big-O). Vamos usar a definição: dizer que h(n)=O(n^{2}) significa que existem constantes c>0 e n_{0} tais que, para todo n\ge n_{0},
h(n)\le c\,n^{2}.

Passo 2

Escrevemos
f(n)+g(n) = \bigl(3n^{2}-n+4\bigr) + \bigl(n\log n+5\bigr) = 3n^{2} + n\log n - n + 9.

Passo 3

Precisamos mostrar que, para n grande, esse somatório fica abaixo de uma constante vezes n^{2}. Note que, para n\ge2, vale
\log n \le n \quad\Longrightarrow\quad n\log n \le n\cdot n = n^{2}.

Passo 4

Além disso, para n\ge1 temos -n\le0 e 9\le9n^{2}. Assim, para todo n\ge2,
f(n)+g(n) =3n^{2} + n\log n -n +9 \le 3n^{2} + n^{2} + 9n^{2} =13\,n^{2}.
Logo, basta escolher c=13 e n_{0}=2 para satisfazer a definição de Big-O.

Resposta

Sim. De fato, f(n)+g(n)=O(n^{2}).\n

Exercícios relacionados