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?
What does the notation $[0,1)$ mean?
-
2Irrelevant tags. – 2012-08-12
-
0@WacDonald's you can edit the tags if you think they are irrelevant . I encountered this while studying algorithms and since this algorithm assumes about probablility distribution of inputs , I put those tags . Since it has to do with sets , the elementary set theory is also justified in my opinion. – 2012-08-12
-
0I have no idea why they chose $[0,1)$ vs $[0,1]$ since they are basically the same in this context (any particular point has zero probability of occurring). – 2012-08-12
-
3The notation is called *half-closed interval.* A closed interval $[0, 1]$ includes the end points $0, 1.$ An open interval $(0, 1)$ does *not* include the end points $0, 1.$ A half-closed interval is closed on one side, open on the other side. So $[0, 1)$ includes $0$ but does not include $1.$ – 2012-08-12
-
1@Geek: It is the usual notation for *intervals*. The interval $[a,b)$ is sometimes called *half-open*, as is $(a,b]$. The interval $(a,b)$ is an *open* interval, while $[a,b]$ is a *closed* interval. – 2012-08-12
-
0BTW the question "*why* Cormen et al choose $[0, 1)$ over $[0, 1]$" is indeed on topic for math.SE, but might be more suitable for the [Computer Science Beta Stackexchange](http://cs.stackexchange.com/). – 2012-08-12
-
1In Section 15.3 they define a closed interval along with notation, they mention open and half-open intervals but do not provide notation. – 2012-08-12
-
0A late comment, but I've also heard this referred to as a "clopen" interval by a topologist... – 2013-06-27
3 Answers
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 ;-).
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)$$
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.
-
0What this notation is called ? – 2012-08-12
-
2Interval notation? – 2012-08-12
-
14I never saw the second notaion... – 2012-08-12
-
1It is less common, and I have not seen it in a North-American-style calculus book. But one does see it more frequently nowadays. For me it is visually a little harder to separate from the square bracket running the "normal" way. But is probably just a matter of familiarity. – 2012-08-12
-
0I've seen both of them used, though the latter much, much more seldom, and I don't even remember where. It has the advantage that it makes an open interval distinguishable from ordered pair (which the former doesn't, unless you write an ordered pair with triangular bracket...), but the disadvantage that, well, it doesn't parse well, if you know what I mean. – 2012-08-12
-
8I have tended to think of the second notation as the "French" notation, but I don't know how accurate that is. – 2012-08-12
-
0@MichaelHardy I can confirm it is at least used in France. When I moved to NZ I had to adapt to the round bracket notation. – 2012-08-12
-
0I've never seen the former notation myself either, only the latter. – 2012-08-13
-
1I saw the first notation for the first time just a few days ago. In Portugal (from other comments, as in France, Denmark, and probably the rest of Europe, obviously except the UK) $[0;\ 1[$ is used. It must be another anglophonic awkwardness. – 2013-06-10
-
3I think the second notation was introduced by the Bourbaki in order to prevent confusion with ordered pairs. – 2013-07-02
-
0I've run across the second notation, though the former is far more common in the United States. – 2015-05-06
-
0I 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