I'm having some hard times making a tight analysis of the memory requirements for my algorithm. I want to show the following inequality, which will show my data structure can use about 2 bits per counter more than the information theoretic lower bound (if we choose $x,m$ carefully), but I'm not sure this is correct.

Formally, Is it true that:

$$\forall x>m\in\mathbb N:(\lceil\log x\rceil - \left\lfloor\log m\right\rfloor)\cdot m+2^{\lfloor\log m\rfloor+1}\leq m\cdot\left(\left\lceil\log\frac{x}{m}\right\rceil+2\right)$$

When I was going over it yesterday, I thought this inequality, from a previous question would be enough, but I don't see now how to complete the proof. It follows immediately if I replace the "+2" by "+3", but I want the analysis to be tight if possible.

Is this inequality true?


Take, for example, $x=33, m=6$. We then have $\lceil \log x \rceil =6$, $\lfloor \log m \rfloor=2$, $\lceil\log \frac{x}{m}\rceil=\lceil \log 5.5\rceil=3$.

$x>m$ is obviously fulfilled as well.

Putting that in to your inequality, we have $$ (\lceil\log x\rceil - \left\lfloor\log m\right\rfloor)\cdot m+2^{\lfloor\log m\rfloor+1}=(6-2)\cdot 6+2^3=32\leq 30=6\cdot(3+2)= m\cdot\left(\left\lceil\log\frac{x}{m}\right\rceil+2\right), $$

contradiction. So no, your inequality does not hold.

The way you can construct your counterexample is actually more or less working the proof of your mentioned previous question backwards. You find $x,m$ such that $\lceil\log \frac{x}{m}\rceil=\lceil\log x\rceil - \lfloor\log m \rfloor -1$ (namely by choosing $x$ just a bit above and $m$ just a bit below a power of $2$), and then utilize that $2^{\lfloor \log m \rfloor +1}>m$.

| cite | improve this answer | |

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.