[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. \frac{1}{4} n+\cos (n) \notin O(n)
Passo 1
O enunciado pede que digamos se a afirmação
\frac{1}{4}n+\cos(n)\notin O(n)
é verdadeira ou falsa. Ou seja, precisamos verificar se a função f(n)=\frac{1}{4}n+\cos(n) NÃO pertence à classe assintótica O(n). As informações dadas são apenas a expressão de f(n) (não há mais condições).
Passo 2
Vou lembrar a definição de O (Big‑O) de forma clara e simples, passo a passo. Dizemos que uma função g(n) pertence a O(h(n)) se existem constantes positivas C e n_0 tais que, para todo n\ge n_0,
|g(n)| \le C\cdot h(n).
Aqui g(n) é a função que queremos comparar, h(n) é a função de crescimento de referência, C é um multiplicador fixo que permite uma folga, e n_0 é a partir de qual ponto a desigualdade vale para todo n. Nosso caso é g(n)=\frac{1}{4}n+\cos(n) e h(n)=n. Se encontrarmos C>0 e n_0 que satisfaçam a desigualdade, então g(n)\in O(n). Se não for possível, então g(n)\notin O(n).
Passo 3
Vamos analisar a função f(n)=\frac{1}{4}n+\cos(n). Um fato simples e importante: para todo n real,
|\cos(n)| \le 1.
Esse é um limite universal e muito útil: o termo oscilatório \cos(n) é sempre bounded entre -1 e 1.
Agora, para n\ge 1 podemos comparar o termo constante 1 com n: como 1 \le n quando n\ge 1, obtemos
\frac{1}{4}n + 1 \le \frac{1}{4}n + n = \frac{5}{4}n.
Juntando as duas desigualdades:
\left|\frac{1}{4}n+\cos(n)\right| \le \frac{5}{4}n \quad\text{para todo } n\ge 1.
Passo 5
A desigualdade do passo anterior mostra exatamente a condição da definição de Big‑O: basta escolher C=\frac{5}{4} e n_0=1. Então existem constantes positivas C e n_0 tais que, para todo n\ge n_0,
\left|\frac{1}{4}n+\cos(n)\right| \le C\cdot n.
Portanto \frac{1}{4}n+\cos(n)\in O(n). Como a afirmação do enunciado dizia que essa função NÃO pertence a O(n), a afirmação do enunciado é falsa.