Prove $\left\lfloor n\right\rfloor = n + O(1)$

Question

Can someone show me why $\left\lfloor n\right\rfloor = n + O(1)$.

Using the same logic, can anyone derive a similar proposition for $\left\lceil n\right\rceil$?

Answer 1

The reason we use the notation $O(1)$ is that the error associated with performing this operation is constant (i.e. doesn't depend on our value of $n$).

We know that

$\left\lfloor n \right\rfloor = n - m$

where $0\leq m < 1$. For instance,

$\left\lfloor 6.5 \right\rfloor = 6 = 6.5 - 0.5$

The error, $m$ in this case is bound between $0$ and $1$.

If we were too look at much larger numbers, that error bound would be the same. For instance

$\left\lfloor 999234.712 \right\rfloor = 999234 = 999234.712 - 0.712$

Our error is still constant in that it doesn't increase as the number we put in the function increases.

Using this exact same logic and the expression

$\left\lceil n \right\rceil = n + m$

where $0< m \le 1$.

the exact same argument holds.