16

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?

Ricardo Altamirano
  • 137
Geek
  • 2,349
  • 2
    Irrelevant tags. – WacDonald's Aug 12 '12 at 16:44
  • @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. – Geek Aug 12 '12 at 16:51
  • I 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). – copper.hat Aug 12 '12 at 16:55
  • 3
    The 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.$ –  Aug 12 '12 at 16:56
  • 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. – André Nicolas Aug 12 '12 at 16:56
  • BTW 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. –  Aug 12 '12 at 17:00
  • 1
    In Section 15.3 they define a closed interval along with notation, they mention open and half-open intervals but do not provide notation. – copper.hat Aug 12 '12 at 17:03
  • A late comment, but I've also heard this referred to as a "clopen" interval by a topologist... – apnorton Jun 27 '13 at 15:10

3 Answers3

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<b\}=(a,b)$$

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

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

$$\{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\}=(a,\infty)$$

$$\{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)$$

Martin Sleziak
  • 53,687
Pedro
  • 122,002
29

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.

Niel de Beaudrap
  • 6,033
André Nicolas
  • 507,029
  • What this notation is called ? – Geek Aug 12 '12 at 16:52
  • 2
    Interval notation? – GEdgar Aug 12 '12 at 17:02
  • 15
    I never saw the second notaion... – Belgi Aug 12 '12 at 19:16
  • 2
    It 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. – André Nicolas Aug 12 '12 at 19:23
  • I'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. – tomasz Aug 12 '12 at 22:23
  • 9
    I have tended to think of the second notation as the "French" notation, but I don't know how accurate that is. – Michael Hardy Aug 12 '12 at 23:54
  • @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. – Thomas Aug 12 '12 at 23:58
  • I've never seen the former notation myself either, only the latter. – kba Aug 13 '12 at 03:30
  • 1
    I 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. – JMCF125 Jun 10 '13 at 20:27
  • 4
    I think the second notation was introduced by the Bourbaki in order to prevent confusion with ordered pairs. – Vincent Pfenninger Jul 02 '13 at 19:36
  • I've run across the second notation, though the former is far more common in the United States. – anomaly May 06 '15 at 17:25
  • I agree with @VincentPfenninger the "French" notation $\left[ 0,1 \right[$ was introduced by Bourbaki. The notation $\left[ 0,1 \right)$ appears to be older. – Jeppe Stig Nielsen May 29 '17 at 09:29
6

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 ;-).

Pedro
  • 983
  • 1
  • 6
  • 19