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
    what is $\Omega(g(x))$?2010-10-24
  • 0
    $\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.2010-10-24
  • 0
    Do you want to prove this when $x \to \infty$?2010-10-24
  • 0
    @Planeman: $\lfloor{x\rfloor} + \Bigl\lfloor{x + \frac{1}{2}\Bigr\rfloor} = \lfloor{2x\rfloor}$2010-10-24
  • 0
    @svenkatr: I'm not sure how that applies here. You are just trying to bound this function between two other functions.2010-10-24
  • 0
    @Chandru1: Could you tell me how I am supposed to use that? My main problem is that I'm not sure how to apply the regular proof strategies for these problems (Usually polynomials or logs) for the floor function. With that identity I would still be stuck proving that $\lfloor{2x\rfloor}$ is $\theta(x)$.2010-10-24
  • 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