I was wondering if the following inequality is true:

$$\forall x,N\in \mathbb N^+: \lceil \log_2\left(\lfloor\frac{N}{x}+1\rfloor\right)\rceil\leq \lceil\log_2 (N+1)\rceil - \lfloor\log_2 (x)\rfloor $$

I need this inequality to hold for my algorithm analysis: I need to store counter which could reach value $$\lfloor\frac{N}{x}\rfloor$$ using $$\lceil\log_2 (N+1)\rceil - \lfloor\log_2 (x)\rfloor$$


(I've tried it using various values of $x,N$ and it seems to work). Thanks !

  • $\begingroup$ Why was the question downvoted :(? What is wrong with it? $\endgroup$ – Ar Co Jan 29 '15 at 10:08
  • $\begingroup$ It was downvoted before the edit, I think. $\endgroup$ – TonyK Jan 29 '15 at 10:08
  • $\begingroup$ You can't allow $i = M$. $\endgroup$ – TonyK Jan 29 '15 at 10:09
  • $\begingroup$ @TonyK - good point, thanks! I've replaced $M-i$ by $x$, it is also more understandable now. $\endgroup$ – Ar Co Jan 29 '15 at 10:16

We use the following lemma: $\lceil x+y \rceil \le \lceil x\rceil + \lceil y\rceil.$

Proof of the log inequality:

Case 1. When $x$ divides $N$. $k=N/x$ is an integer. \begin{align*} \text{LHS}&=\left\lceil\log_2 (k+1)\right\rceil\\ &=\left\lceil\log_2 (k+1/x)\right\rceil\\ &= \left\lceil\log_2 (N+1)-\log_2 x\right\rceil\\ &\le \left\lceil\log_2 (N+1)\right\rceil+\left\lceil (-\log_2 x)\right\rceil\\ &= \left\lceil\log_2 (N+1)\right\rceil-\left\lfloor \log_2 x\right\rfloor=\text{RHS}. \end{align*}

Case 2. When $x$ doesn't divide $N$. $k=\lceil N/x\rceil$ is an integer. Since $(k-1)x<N\le kx$, $k-1+\frac1x<\frac{N+1}{x}\le k+\frac1x$. \begin{align*} \text{LHS}&=\left\lceil\log_2 k\right\rceil\\ &=\left\lceil\log_2 (k-1+1/x)\right\rceil\\ &\le \left\lceil(\log_2 \frac{N+1}{x})\right\rceil\\ &=\left\lceil\log_2 (N+1)-\log_2 x\right\rceil\\ &\le \left\lceil\log_2 (N+1)\right\rceil+\left\lceil (-\log_2 x)\right\rceil\\ &= \left\lceil\log_2 (N+1)\right\rceil-\left\lfloor \log_2 x\right\rfloor=\text{RHS}. \end{align*}

| 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.