title: Finding the probability that two items are compared. (hints please)
body: <p>I'm attempting to solve the following problem (from Prof. Jeff Erikson's notes): Given the algorithm below which takes in an unsorted array A and returns the k-th smallest element in the array (given that Partition does what its name implies via the standard quicksort method given the pivot returned by Random (which is assumed to return a uniformly random integer between 1 and n in linear time) and returns the new index of the pivot), we are to find the <em>exact</em> probability that this algorithm compares the i-th smallest and j-th smallest elements in the input array.</p>
  
  <pre><code>QuickSelect(A[1..n],k):
    r &lt;-- Partition(A[1..n],Random(n))
  
    if k &lt; r:
      return QuickSelect(A[1..r-1],k)
    else if k &gt; r:
      return QuickSelect(A[r+1..n],k-r)
    else:
      return A[k]
  </code></pre>
  
  <p>Now, I can see that the probability of the first if statement being true is (n-k)/n, the probability of the second block being true is (k-1)/n, and the probability of executing the else statement is 1/n. I also know that (assuming i &lt; j) the probability of i &lt; r &lt; j is (j-i-1)/n which guarantees that the two elements are never compared. On the other hand, if i==r or j==r, then i and j are guaranteed to be compared. The part that really trips me up is what happens if r &lt; i or j &lt; r, because whether or not i and j are compared depends on the value of k (whether or not we are able to recursively call QuickSelect). </p>
  
  <p>Any hints and/or suggestions would be greatly appreciated. This <em>is</em> for homework, so I would rather not have full solutions given to me so that I may actually learn a bit. Thanks in advance!</p>