Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 1

up vote 1 down vote accepted

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?

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.