0
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ @StevenStadnicki Yes, I mean floor on both sides. $\endgroup$ – Student Nov 8 '17 at 22:01
  • $\begingroup$ A hint, then: where does $\lfloor\mathop{lg}(n)\rfloor$ change? $\endgroup$ – Steven Stadnicki Nov 8 '17 at 22:02
  • $\begingroup$ @StevenStadnicki What do you mean with where does ⌊lg(n)⌋ change ? $\endgroup$ – Student Nov 8 '17 at 22:09
  • $\begingroup$ 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$? $\endgroup$ – Steven Stadnicki Nov 8 '17 at 22:12
  • $\begingroup$ @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 ? $\endgroup$ – Student Nov 8 '17 at 22:22
1
$\begingroup$

$\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

$\endgroup$

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.