# $\left \lfloor{\log(n-1)}\right \rfloor$ = $\left \lfloor{\log(n)}\right \rfloor$ for n odd

I have been trying to prove the worst case for the binary-search algorithm. During the proof I came to this equality: $\left \lfloor{\log(n-1)}\right \rfloor$ = $\left \lfloor{\log(n)}\right \rfloor$ for n odd(here lg means logarithm with base 2). Can anyone help me with proving this equality ?

• @StevenStadnicki Yes, I mean floor on both sides. – Student Nov 8 '17 at 22:01
• A hint, then: where does $\lfloor\mathop{lg}(n)\rfloor$ change? – Steven Stadnicki Nov 8 '17 at 22:02
• @StevenStadnicki What do you mean with where does ⌊lg(n)⌋ change ? – Student Nov 8 '17 at 22:09
• I mean this: the function $f(n)=\lfloor\lg(n)\rfloor$ takes on only integer values (because that's the nature of the floor function). Where does it change from having the value $t$ to having the value $t+1$? – Steven Stadnicki Nov 8 '17 at 22:12
• @StevenStadnicki From what I can see the function f(n) in order to have a value t+1 instead of t, the input for the function should be 2(n-1) instead of n. So, in this case because n and (n-1) do not have that much difference the posted equality holds ? – Student Nov 8 '17 at 22:22

## 1 Answer

$\lfloor \log_2(n) \rfloor = k$ means that

$k\leq \log_2(n) < k+1$

It follow that

$2^k \leq n < 2^{k+1}$

But $n$ is odd, $n \neq 2^k$, hence $2^k < n$,and as both are integers, $2^k \leq n-1$ hence

$2^k \leq n-1 < 2^{k+1}$

So $k< \log_2(n-1) <k+1$ and we have the result