Originally Posted by

**awkward** Hi,

Here is an observation that you may find helpful.

The tricky point about this algorithm is the test "a[i] > mx". Let's fix i and ask the question, "What is the probability that a[i] > mx, given that a[] initially contains a random permutation of 0, 1, ..., n-1?"

Inspection of the algorithm shows that a[i] > mx exactly when a[i] is the largest value seen so far, i.e. a[i] is the maximum of a[0], a[1], a[2], ... , a[i]. So what's the probability? Well, when i=1, the probability that a[1] is greater than a[0] is 1/2. When i=2, the probability that a[2] is the largest of a[0], a[1], and a[2] is 1/3, because each of a[0], a[1], and a[2] is equally likely to be the largest. And in general, the probability that a[i] is the maximum of a[0], a[1], a[2], ..., a[i] is 1/(i+1).

So the probability that a[i] > mx is 1/(i+1).