# Proving theta complexity for floor function

How can you prove that $\Bigl\lfloor{x + \dfrac{1}{2}}\Bigr\rfloor$ is a $\theta(x)$ function?

I'm just practicing questions that could come up on an exam and this one was giving me a tough time trying to formally prove it.

$f(x)$ is $\theta(g(x)) \leftrightarrow f(x)$ is $O(g(x))$ and $f(x)$ is $\Omega(g(x))$

-
what is $\Omega(g(x))$? – anonymous Oct 24 '10 at 18:12
$\Omega(g(x))$ is the lower bound on the function. Essentially the last thing I said there is that if the upper bound is $O(g(x))$ and the lower bound is $\Omega(g(x))$ are both true then $f(x)$ is $\theta(g(x))$ complexity. – Planeman Oct 24 '10 at 18:19
Do you want to prove this when $x \to \infty$? – svenkatr Oct 24 '10 at 18:22
@Planeman: $\lfloor{x\rfloor} + \Bigl\lfloor{x + \frac{1}{2}\Bigr\rfloor} = \lfloor{2x\rfloor}$ – anonymous Oct 24 '10 at 18:24
@svenkatr: I'm not sure how that applies here. You are just trying to bound this function between two other functions. – Planeman Oct 24 '10 at 18:28

## 1 Answer

You can write

$$x - \frac{1}{2} \leq \Bigl\lfloor x+\frac{1}{2}\Bigr\rfloor \leq x+\frac{1}{2}$$

Doesn't this give you the result?

-
Yeah that works and I had written something down similar to that but it didn't seem that would be sufficient for a "formal" proof. You are correct with that statement though. – Planeman Oct 24 '10 at 18:39