3
$\begingroup$

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

Bits.

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

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

1 Answer 1

0
$\begingroup$

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*}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .