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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communitycan 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.
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.