16
$\begingroup$

I am studying the procedure for bucket sort from Introduction To Algorithms by Cormen et al, which assumes that the input is generated by a random process that distributes the elements uniformly and independently over the interval $[0,1).$ What does this mean? Why there is no "]" closing bracket for the interval?

  • 0
    A late comment, but I've also heard this referred to as a "clopen" interval by a topologist...2013-06-27

3 Answers 3

4

This means that your interval goes from 0 to 1 but 1 itself is not included in the interval. You're random number process will generate a number between 0 and 1 (1 not included). We call this a half closed interval. Sometimes they write in textbooks [0,1[ in stead of [0,1), that's the same.

Sorry if the explanation is not mathematical enough. I'm a computer scientist ;-).

32

In general, there are four possible variants for what we call intervals. The parenthesis $($ and $)$ are related to the strict inequality $<$, while these ones $[$ and $]$ are related to the weaker $\leq$. So, when we want to denote intervals, we use them as follows

$\{x \text{ such that } a

$\{x \text{ such that } a\leq x

$\{x \text{ such that } a

$\{x \text{ such that } a \leq x \leq b\}=[a,b]$

You might also see $]a,b[$ for $(a,b)$, that is, the reversed $]$ are used just like parenthesis.

There is also what we call "rays" (which are also intervals), which involve a "one sided" inequality:

$\{x \text{ such that } a

$\{x \text{ such that } a\leq x\}=[a,\infty)$

$\{x \text{ such that } x \leq b\}=(-\infty,b]$

$\{x \text{ such that } x < b\}=(-\infty,b)$

and what we usually denote by the real line

$\{x \text{ such that }x\in \Bbb R \}=(-\infty,\infty)$

26

The notation $[0,1)$ refers to the set of all real numbers $x$ such that $0\le x\lt 1$. Another common notation for this set is $[0,1[$; which is more common often depends on the language in which the author was educated.

  • 0
    I agree with @VincentPfenninger the "French" notation $\left[ 0,1 \right[$ was introduced by [Bourbaki](https://en.wikipedia.org/wiki/Nicolas_Bourbaki). The notation $\left[ 0,1 \right)$ appears to be older.2017-05-29