Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
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.$ –  user2468 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
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
show 3 more comments

3 Answers

up vote 18 down vote accepted

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.

share|improve this answer
    
What this notation is called ? –  Geek Aug 12 '12 at 16:52
2  
Interval notation? –  GEdgar Aug 12 '12 at 17:02
11  
I never saw the second notaion... –  Belgi Aug 12 '12 at 19:16
    
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
7  
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
show 5 more comments

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 se $]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)$$

share|improve this answer
    
+1 for mentioning about the other related notations . –  Geek Aug 12 '12 at 16:58
    
+1 for completeness. –  Wayne Werner Aug 12 '12 at 23:05
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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