1
$\begingroup$

I went through the Master Theorum extension for floors and ceiling section 4.6.2 in the book Introduction to Algorithms

It had the following statement:

Using the inequality $\lceil x \rceil \le x+1$

But I haven't seen the inequality anywhere and could not understand the verifiability of inequality.

Instead the Chapter Floors and ceilings defined floors and ceilings as:

$$x-1 \lt \lfloor x \rfloor \le x \le \lceil x \rceil \lt x+1 $$

Please clear my doubt over this.

On how to use this identity and which identity to be considered when because both of them define completely different inequalities.

Thank you.

$\endgroup$
  • $\begingroup$ The inequality $\lceil x \rceil < x+1$ is stronger than $\lceil x \rceil \leq x+1$, but both are valid. $\endgroup$ – Yuval Filmus Jul 1 at 16:49
2
$\begingroup$

The definition of $\lceil x \rceil$ is:

$\lceil x \rceil$ is the minimal integer $n$ such that $n \geq x$.

(The existence of such an integer makes the reals an Archimedean field.)

Let us assume, for the sake of contradiction, that $\lceil x \rceil \geq x + 1$. Then $\lceil x \rceil - 1 \geq x$. Since $\lceil x \rceil - 1$ is also an integer, this contradicts the definition of $\lceil x \rceil$. Thus $\lceil x \rceil < x + 1$.

It is also easy to check that the inequality is tight, in the sense that $1$ cannot be replaced by any smaller $\theta$. Indeed, if $\theta = 1 - \epsilon$ for $\epsilon \in (0,1)$, then $\lceil \epsilon \rceil = 1 = \epsilon + \theta$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ AFAIK the contradiction proves that the inequality is wrong isn't it. $\endgroup$ – Sachin Bahukhandi Jul 1 at 15:28
  • $\begingroup$ No, the inequality is correct. $\endgroup$ – Yuval Filmus Jul 1 at 15:31
  • $\begingroup$ Okay but the chapter floors and ceilings gave a different perspective on floors and ceilings. $\endgroup$ – Sachin Bahukhandi Jul 1 at 15:36
  • 1
    $\begingroup$ @SachinBahukhandi $a \leq b$ is usually defined as $(a < b) \lor a = b$. Hence to show $a = b$ or $a < b$ is enough to show $a \leq b$. $\endgroup$ – Novicegrammer Jul 1 at 16:30
  • 1
    $\begingroup$ You mean that $a \leq b$ follows from $a < b$, or from $a = b$. In particular, if we know that $a < b$, then it follows that $a \leq b$. $\endgroup$ – Yuval Filmus Jul 1 at 16:48

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.