This question already has an answer here:

can someone pls help

How do I prove

2⌊lg n⌋ = Θ(2⌈lg n⌉)

2 ⌈lg n⌉+⌊lg n⌋ = Θ(n2)

I'm not too good at maths. I know,

lim ( n -> infinty) = f(x)/g(x) if we get a real constant the statement is true.


marked as duplicate by David Richerby, Raphael algorithms Jan 28 '18 at 20:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ You prove the first one by using the definition of $\Theta$; you don't prove the second one at all, because it isn't true. $\endgroup$ – David Richerby Jan 28 '18 at 17:17
  • $\begingroup$ @DavidRicherby i just wanted to know how does limit for floor and ceiling function work as by defn. if limit is (c,infinity) the it is big theta $\endgroup$ – Sandeep Ranjan Jan 28 '18 at 18:00
  • $\begingroup$ You might need to ask a more specific question, then. If it's only about the mathematics, you should ask it on Mathematics. $\endgroup$ – Raphael Jan 28 '18 at 20:58

First, observe that $\lfloor \log N \rfloor < 2\lceil \log N \rceil$ holds for all $N \geq 2$.
Let $n_0 = 2$, $c_1=2$, $f(N)=2\lfloor \log N \rfloor$, $g(N) = 2\lceil \log N \rceil$.
So $$f(N) \leq c_1 \cdot g(N)$$ holds for all $N \geq n_0$.
Next, observe that $\lfloor \log N \rfloor > \frac{1}{2}\lceil \log N \rceil$ is true for all $N \geq 2$.
Let $c_2 = \frac{1}{2}$.
Thus, $$f(N) \geq c_2 \cdot g(N)$$ Therefore, $$f(N) \in \Theta(g(N))$$ But the second question, it is obvious that the statement is incorrect, so I'll not be proving here.


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