Proving that, if a function f is O(g), the ceiling of f is also O(g).

Question

I'm having a bit of trouble with this problem:

$$\forall (f, g) \in F, f \in O(g) \implies \lceil{f}\rceil \in O(g)$$

Where F is the family of functions from $\mathbb{N}$ to $\mathbb{R}^+$.

I know that $f(n) \leq \lceil{f(n)}\rceil \leq f(n)+1$, since the next int that fits is always less than 1 unit away.

I'm kind of stuck on how to show $f(n) + 1 \leq cg(n)$, using the definition: $$\exists c > 0, \exists n_0, \forall n, n \geq n_0 \implies f(n)+1 \leq cg(n)$$

Any guidance would be greatly appreciated. Thanks!

The statement is only true if the limit of $g$ is not $0$... — 5xum, Aug 01 '14 at 07:32
@5xum limes inferior ... so this is true if $g$ is bounded below. — martini, Aug 01 '14 at 07:34

score 8 · Accepted Answer · answered Aug 01 '14 at 07:27

The statement you want to prove is wrong. Let $g(n) = f(n) = \frac 1{n}$. Then $\lceil f\rceil(n) = 1$ for all $n$. Obviously $f \in O(g)$, but there is no $c$ such that $1 \le \frac cn$ for almost all $n$, as this is equivalent to $n \le c$. So $\lceil f\rceil \not\in O(g)$.

Proving that, if a function f is O(g), the ceiling of f is also O(g).

1 Answers1