1
$\begingroup$

The problem is IV-3 of this pdf: potential function.

Defining a potential function as $\Phi(i) = 2i - 2^{\lfloor{\log_2i}\rfloor+1} + 1$

The solution states that if $i$ is not an exact power of $2$, we have:

$$\Phi(i) = 2i - i + 1 .$$

This means that $2^{\lfloor{\log_2i}\rfloor+1} = i$. I'm having some trouble understanding this equality.

Can somebody shed some light?

$\endgroup$
  • $\begingroup$ This equation doesn't hold. You can try it with $i=3$, for example: $2^{\lfloor \log_23 \rfloor+1} = 2^{1+1} = 4$. $\endgroup$ – Yuval Filmus Mar 26 '17 at 15:58
5
$\begingroup$

The analysis there is slightly wrong, though the conclusions are correct. Here is the correct calculation:

  1. $i$ is not a power of 2. In that case $\lfloor \log_2 i \rfloor = \lfloor \log_2 (i-1) \rfloor$ and so $\Phi(i) - \Phi(i-1) = (2i+1) - (2(i-1)+1) = 2$.
  2. $i$ is a power of 2. In that case $2^{\lfloor \log_2 i \rfloor} = i$ and $2^{\lfloor \log_2 (i-1) \rfloor} = i/2$, and so $\Phi(i) - \Phi(i-1) = (2i - 2i + 1) - (2(i-1) - i + 1) = 2-i$.
$\endgroup$
  • $\begingroup$ Just a small correction, the last result should be $-i + 2$ $\endgroup$ – joaoaccarvalho Mar 26 '17 at 17:33

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.