2
$\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$
1
  • $\begingroup$ The inequality $\lceil x \rceil < x+1$ is stronger than $\lceil x \rceil \leq x+1$, but both are valid. $\endgroup$ Jul 1, 2020 at 16:49

1 Answer 1

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

$\endgroup$
11
  • $\begingroup$ AFAIK the contradiction proves that the inequality is wrong isn't it. $\endgroup$ Jul 1, 2020 at 15:28
  • $\begingroup$ No, the inequality is correct. $\endgroup$ Jul 1, 2020 at 15:31
  • $\begingroup$ Okay but the chapter floors and ceilings gave a different perspective on floors and ceilings. $\endgroup$ Jul 1, 2020 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$ Jul 1, 2020 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$ Jul 1, 2020 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.