3
$\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$
2
  • 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, 2019 at 22:23
  • $\begingroup$ Please check my answer, I think that your statement needs a small correction. $\endgroup$
    – Saša
    Apr 24, 2019 at 8:17

1 Answer 1

1
$\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$
1
  • $\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$ Apr 24, 2019 at 22:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .