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)=\lfloor x\rfloor

Passo 1

O enunciado pede para mostrar que f(x)=\lfloor x\rfloor é O(x), ou seja, encontrar constantes C e k tais que
|f(x)| \le C\,|x|
sempre que x>k. Aqui g(x)=x.

Passo 2

Para todo x>0 vale
\lfloor x\rfloor \le x,
e como \lfloor x\rfloor\ge0 também temos |\lfloor x\rfloor|=\lfloor x\rfloor. Logo
|\lfloor x\rfloor|\le x = 1\cdot|x|.

Passo 3

Basta então escolher
C=1 \quad\text{e}\quad k=0
(ou qualquer k\ge0), pois para todo x>k temos
|f(x)|=|\lfloor x\rfloor|\le1\cdot|x|.
Isto mostra que \lfloor x\rfloor cresce no máximo na mesma ordem que x.

Resposta

C=1,\;k=0 e, portanto, \lfloor x\rfloor\in O(x).

Exercícios de Livros Relacionados