# Asymptotic notation? [duplicate]

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 StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jan 28 '18 at 20:56

• 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. – David Richerby Jan 28 '18 at 17:17
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.