[1 pt] Para cada afirmação abaixo, informe se ela é verdadeira ou falsa. Use a notação assintótica para desenvolver e justificar a sua resposta.
3 n(n+2) \neq O\left(n^{3}\right)

Passo 1

O enunciado apresenta a afirmação
3 n(n+2) \neq O\left(n^{3}\right)
e pede que eu informe se essa afirmação é verdadeira ou falsa, usando notação assintótica e justificando a resposta.
Informações dadas: a expressão 3 n(n+2) e a comparação com n^{3}. Não há outras condições explícitas, então entendemos n como variável que tende a infinito (ou n\in\mathbb{N}, n\to\infty).

Passo 2

Vou recordar a definição de O (Big‑O) de forma clara e simples. Dizemos que uma função f(n) é O(g(n)) se existem constantes positivas c e n_{0} tais que, para todo n\ge n_{0},
|f(n)| \le c\,|g(n)|.
Aqui c é uma constante que “amortece” a diferença de escala entre f e g, e n_{0} é a partir de que ponto essa desigualdade passa a valer para todos os n maiores. Em linguagem informal: f(n) cresce no máximo tão rápido quanto g(n), até uma constante multiplicativa, para n grandes.

Passo 3

Escrevo a função em forma polinomial para ficar mais claro o termo dominante:
3 n(n+2) = 3(n^{2}+2n) = 3n^{2}+6n.
Ou seja, f(n)=3n^{2}+6n.

Passo 4

Agora vou encontrar uma desigualdade do tipo f(n) \le c\, n^{3} válida para n grandes. Para n\ge 1 valem as desigualdades simples
n \le n^{2}\qquad\text{e}\qquad n^{2} \le n^{3},
pois multiplicar por n\ge1 preserva/desloca para cima. Usando essas relações, tenho para n\ge 1:
3n^{2}+6n \le 3n^{2} + 6n^{2} = 9n^{2}.
E, como n^{2}\le n^{3} para n\ge1, segue
9n^{2} \le 9n^{3}.
Compondo as desigualdades obtemos, para todo n\ge 1,
3n^{2}+6n \le 9n^{3}.

Passo 5

A desigualdade do passo anterior mostra que podemos escolher c=9 e n_{0}=1 e satisfazemos a definição de Big‑O:
\forall n\ge n_{0}=1,\quad |3n(n+2)| = 3n^{2}+6n \le 9 n^{3} = c\, n^{3}.
Portanto 3n(n+2)=O(n^{3}).

Passo 6

Como eu acabei de provar que 3n(n+2)=O(n^{3}) (exibindo c e n_{0}), a afirmação dada no enunciado, que nega essa relação, não é correta. Para reforçar a intuição, uma verificação alternativa é calcular o limite do quociente:
\lim_{n\to\infty}\frac{3n^{2}+6n}{n^{3}}=\lim_{n\to\infty}\left(\frac{3}{n}+\frac{6}{n^{2}}\right)=0,
o que também indica que o quociente é limitado (na verdade tende a 0), logo 3n(n+2)=O(n^{3}).

Resposta

Falso.

Exercícios relacionados