Question

This is a probabilistic analysis of algorithms question.

Consider the following randomized version of quick_select() which returns the k^th smallest element of an unsorted array:

        random_partition(A[lo..hi], rindex)
        {
                swap(A[hi], A[rindex]);
                i = lo;
                for (j = lo; j < hi; ++j)
                        if (A[j] < A[hi])
                                swap(A[i++], A[j]);
                swap(A[i], A[hi]);
                return i;
        }

        random_quick_select(A[lo..hi], k)
        {
                if (lo == hi)
                        return A[lo];
                p = random_partition(A[lo..hi], rand(lo, hi));
                prank = p - lo + 1;
                if (prank == k)
                        return A[p];
                if (prank > k)
                        return random_quick_select(A, lo, p-1, k);
                else
                        return random_quick_select(A, p+1, hi, k-prank);
        }

Show that the expected number of array element comparisons by random_quick_select() is O(n).

Answer 1

So Basically, the algorithm can be summarised in below

Given array A of size n and integer k ≤ n,
   1. Pick a pivot element p at random from A.
   2. Split A into subarrays LESS and GREATER by comparing each element to p as in
           Quicksort. While we are at it, count the number L of elements going in to LESS.
   3. (a) If L = k − 1, then output p.
           (b) If L > k − 1, output QuickSelect(LESS, k).
           (c) If L < k − 1, output QuickSelect(GREATER, k − L − 1)

Proof for Expected number of comparisions
-----------------------------------------------------------
Let T(n, k) denote the expected time to find the kth smallest in an array of size n,
and let T(n) = maxk T(n, k).

We will show that T(n) < 4n.

First of all, it takes n−1 comparisons to split into the array into two pieces in Step 2.

These pieces are equally likely to have size 0 and n − 1, or 1 and n − 2, or 2 and n − 3,
and so on up to n − 1 and 0.

The piece we recurse on will depend on k, but since we are only giving an upper bound, we
can imagine that we always recurse on the larger piece.

Therefore we have:

(.......summation is over T(i) , the summation symbol below has shifted slightly above the line , assume to be inline)
T(n) ≤ (n − 1) + (2/n) T(i)
= (n − 1) + avg [T(n/2), . . . , T(n − 1)] .

We can solve this using the “guess and check” method based on our intuition above.

Assume inductively that T(i) ≤ 4i for i < n.

Then,
T(n) ≤ (n − 1) + avg [4(n/2), 4(n/2 + 1), . . . , 4(n − 1)]
       ≤ (n − 1) + 4(3n/4)
       < 4n,
and we have verified our guess

hence the Expected Number of comparisions turns out to be O(n).