0
$\begingroup$

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))$

  • 0
    @Planeman: Its just an identity. By the way if you want a bound for $\Bigl\lfloor{x + \frac{1}{2}\Bigr\rfloor}$ if think you take your $g(x)$ to be $2x$2010-10-24

1 Answers 1

1

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?

  • 0
    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.2010-10-24