[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 \log (n) \in O\left(n^{2}\right)

Passo 1

O enunciado dá a afirmação
3 n \log(n) \in O\bigl(n^{2}\bigr).
Lista do que foi dado e do que se pede:
  • Função a comparar: \;f(n)=3 n \log(n).
  • Função de referência: \;g(n)=n^{2}.
  • Pergunta: a afirmação é verdadeira ou falsa? Ou seja, existe constante C>0 e n_{0} tais que, para todo n\ge n_{0},
0 \le f(n) \le C\,g(n)\,?

Passo 2

Definição de O(\cdot) (Big‑O), explicada devagarinho: dizemos que f(n)\in O(g(n)) se existem constantes C>0 e n_{0} tais que, para todo n\ge n_{0},
0 \le f(n) \le C\,g(n).
Aqui f(n) e g(n) são funções não negativas para n suficientemente grande; C é um multiplicador constante e n_{0} é o ponto a partir do qual a desigualdade vale sempre. Nosso objetivo é achar tais C e n_{0} (ou provar que não existem).

Passo 3

Uma desigualdade útil sobre logaritmos que usamos com frequência: para n\ge 1 vale
\log(n)\le n.
Pequena justificativa: considere \varphi(n)=n-\log(n). Então \varphi'(n)=1-\tfrac{1}{n}\ge 0 para n\ge1, logo \varphi é crescente em [1,\infty) e \varphi(1)=1, portanto \varphi(n)\ge 1>0 para n\ge1, o que dá \log(n)\le n.

Passo 4

Multiplicando a desigualdade do passo anterior por 3n (que é não negativo para n\ge 0), obtemos, para n\ge 1,
3 n \log(n) \le 3 n \cdot n = 3 n^{2}.
Ou seja, para todo n\ge 1 temos
0 \le 3 n \log(n) \le 3\, n^{2}.
Portanto podemos escolher as constantes C=3 e n_{0}=1, que satisfazem exatamente a condição da definição de Big‑O.

Passo 5

Resumo do raciocínio: encontramos C=3 e n_{0}=1 tais que, para todo n\ge n_{0}, 3 n \log(n) \le C\,n^{2}. Isso cumpre a definição de f(n)\in O(g(n)).

Resposta

Verdadeira

Exercícios relacionados