Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am given a uniformly chosen permutation of the set $\{1,\ldots,n\}$ as an array $A[1,\ldots,n]$. For an integer $1 \leq j \leq n$ I am studing the distribution of the variable $X$ counting the number of comparisions $(A[i]> key)$ in the above algorithm:

key = A[j]
i = j-1
while (i > 0) and (A[i] > key)
   A[i+1] = A[i]

It is assumed that no comparison is performed when $i \leq 0$. The book I am reading states $Pr[X = k] = 1/j$ for $1 <= k < j-1$ and $Pr[X = j-1] = 2/j$.

There is no explanation why is that so, so I am wondering if anyone could explain to me why is $X$ distributed as stated since I am missing the intuition behind the calculation of this specific probability.

share|cite|improve this question
up vote 2 down vote accepted

When you're doing this step of the insertion sort algorithm, A[1] .. A[j-1] are the original A[1] .. A[j-1] sorted into increasing order. Since the initial permutation was random, the rank of A[j] among A[1] .. A[j] is equally likely to be each of the $j$ possibilities. If A[j] is the $i$'th largest of A[1] .. A[j], the algorithm will compare it to A[j-1], ..., A[j-i], so $X = i$, except that if $i=j$ there is no A[0] to compare it to. Thus for $k = 1, 2, \ldots j-2$ we have $P(X = k) = 1/j$, but $X = j-1$ covers two possibilities ($A[j]$ is either lowest or second-lowest) so $P(X = j-1) = 2/j$.

share|cite|improve this answer

Your Answer


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.