Nos exercícios de 1 a 14, para estabelecer uma relação O grande, encontre os parâmetros C e k, tal que |f(x)| \leq C|g(x)| sempre que x>k.
Determine se cada uma destas funções é O(x).
f(x)=\lceil x / 2\rceil

Passo 1

O enunciado pede para mostrarmos que f(x)=\lceil x/2\rceil é O(x), ou seja, encontrar constantes C>0 e k tais que \lvert f(x)\rvert\le C\lvert x\rvert para todo x>k.

Passo 2

Usamos a propriedade geral de função teto: para todo real t vale
\lceil t\rceil \le t + 1.
Aplicando a t = x/2 segue
\lceil x/2\rceil \le x/2 + 1.

Passo 3

Para x>2 temos 1 \le x/2, portanto
x/2 + 1 \le x/2 + x/2 = x.
Logo, para todo x>2,
\lvert \lceil x/2\rceil\rvert \le x.

Passo 4

Comparando com \lvert x\rvert, vemos que podemos escolher C=1 e k=2, pois para x>k garante-se \lvert f(x)\rvert\le C\lvert x\rvert.

Resposta

C=1,\\ k=2, e portanto \lceil x/2\rceil = O(x).

Exercícios de Livros Relacionados