2
$\begingroup$

We have been doing algorithm analysis in university, and after analyzing binary search algorithm, the following equation resulted. What we have to do now is to prove that $ \left \lfloor {\log n} \right \rfloor = \left \lfloor {\log \left \lceil \frac {n-1}{2}\right \rceil} \right \rfloor + 1$

This has been causing me some headache today and desperately I decided to put it on this forum in hope of some hint that my tunnel sight now may have missed.

At first, I tried to get a proof just by mathimatical transformations. That just didn´t go very well, although I got this $ \left \lfloor {\log n} \right \rfloor = \left \lfloor {\log (\left \lceil \frac {n}{2}\right \rceil*2-2)} \right \rfloor$ which I tried to prove seperately for n even and not even, but I got stuck.

My next approach was considering for n not even -> n-1 is even. And then

$2^k$ $\leq$ n-1 < n < $2^{k+1}$ $\Rightarrow$ $ k \leq log (n-1) < log n < k+1 $

Even though I made a better progress this way, I just can´t relate with the ceiling function inside the logarithm.

Can somebody give me a hint about that? Thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ I'd try putting $n=2^k+t$ where $0\leq t <2^k$, and look at $t=0,1\leq t <2^k$. separately. $\endgroup$ – kingW3 Apr 21 at 22:23
  • $\begingroup$ Please check my answer, I think that your statement needs a small correction. $\endgroup$ – Oldboy Apr 24 at 8:17
0
$\begingroup$

Your original statement is not true (please read the whole answer). But the following statement is correct:

$$\left \lfloor {\log_2 n} \right \rfloor = \left \lfloor {\log_2 \left \lceil \frac {n-1}{2}\right \rceil} \right \rfloor + 1\tag{1}$$

Proof:

Every number $n$ can be placed between two cosecutive powers of 2. In other words, there exists $k$ such that:

$$2^k\le n\le2^{k+1}-1\tag{1}$$

Obviously:

$$k\le\log_2n<k+1$$

$$k=\lfloor\log_2n\rfloor\tag{2}$$

On the other side from (1):

$$\frac{2^k-1}2 \le \frac{n-1}{2} \le \frac{2^{k+1}-2}2$$

$$2^{k-1}-\frac12 \le \frac{n-1}{2} \le 2^k-1$$

$$\lceil 2^{k-1}-\frac12\rceil \le \lceil\frac{n-1}{2}\rceil \le 2^k-1$$

$$2^{k-1} \le \lceil\frac{n-1}{2}\rceil \le 2^k-1$$

$${k-1} \le \log_2\lceil\frac{n-1}{2}\rceil \le \log_2 (2^k-1)<k$$

$${k-1} =\lfloor \log_2\lceil\frac{n-1}{2}\rceil \rfloor$$

$$k=\lfloor \log_2\lceil\frac{n-1}{2}\rceil \rfloor+1\tag{3}$$

By comparing (2) and (3) you get:

$$\lfloor\log_2n\rfloor = \lfloor \log_2\lceil\frac{n-1}{2}\rceil \rfloor+1$$

...which completes the proof.

You can easily prove that the original statement is not true. You are basically saying that the function:

$$f(n)=\left \lfloor {\log n} \right \rfloor - \left \lfloor {\log \left \lceil \frac {n-1}{2}\right \rceil} \right \rfloor - 1$$

...is equal to zero for all values of $n$.

This is not true if "$\log$" stands for logartihm with base 10:

enter image description here

This is also not true if "$\log$" stans for natural logarithm "$\ln$":

enter image description here

If you don't trust these plots, calculate the value for $n=45$ and in both cases the result is -1, not 0.

$\endgroup$
  • $\begingroup$ First of all, thank you very much for your time and help! I figured something out using the method of n even or odd. But this made it all clear. And yes, you were right. I was a bit too tired so that I forgot to mention that log:= log of base 2. $\endgroup$ – infinitedreamer666 Apr 24 at 22:24
  • $\begingroup$ @infinitedreamer666 It’s polite to upvote/accept the answer that you find useful. $\endgroup$ – Oldboy Apr 25 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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