Question

Consider the following algorithm to find the kth largest element of a given array A of n numbers. We pick every fifth element of A and place them in the array B. We find the median of B recursively, and use this median of B as a pivot to partition the array A. Depending on k and the number of elements that are smaller than the chosen pivot, we recurse into an appropriate subproblem of A.

Answer the following questions.

Write the above procedure as a small pseudocode.

Is the algorithm correct? Justify your answer.

Express the worst case run time of this procedure by writing a recurrence relation.

Solve the recurrence relation.

Answer 1

Yes The above algorithm is correct and in-fact it the best algorithm to find Kth largest element in an array in linear time

Algorithm is

1.Divide the array into n/5 groups where size of each group is 5 elements

2.Sort all the above [n/5] created groups and find median of all groups , Also create a median array which needs to store the medians of all n/5 groups

3.Recursively call to find median of medians i.e medofMedian

4.Apply partition algorithm taking result of step 4 as pivot .

pos = partition(arr, n, medOfMedian)

5) If pos == k return medOfMedian
6) If pos > k return kthSmallest(arr[l..pos-1], k)
7) If pos < k return kthSmallest(arr[pos+1..r], k-pos+l-1)

Now pseudocode for above algorithm is

int kthSmallest(int arr[], int s, int l, int k)

{

    // If k is smaller than number of elements in array

    if (k > 0 && k <= l - s+ 1)

    {

        int n = l-s+1; // Number of elements in arr[l..r]

    // Divide arr[] in groups of size 5, calculate median

        // of every group and store it in median[] array.

        int i, median[(n+4)/5];

        for (i=0; i

            median[i] = findMedian(arr+s+i*5, 5);

        if (i*5 < n) //For last group with less than 5 elements

        {

            median[i] = findMedian(arr+s+i*5, n%5);

            i++;

        }    

   // Find median of all medians using recursive call.

        int medOfMedian = (i == 1)? median[i-1]:

                                 kthSmallest(median, 0, i-1, i/2);

// Partition the array around a random element and

        // get position of pivot element in sorted array

        int pos = partition(arr, s, l, medOfMedian);

   // If position is same as k

        if (pos-s == k-1)

            return arr[pos];

        if (pos-1 > k-1) // If position is more, recur for left

            return kthSmallest(arr, s, pos-1, k);

// Else recur for right sub array

        return kthSmallest(arr, pos+1, l, k-pos+s-1);

     // If k is more than number of elements in array

    return INT_MAX;

}

Time complexity taken by this algorithm

Time Taken each of the Five steps

Step 1

Dividing the n elements into n/5 group will take constant time i.eO(1)

Step 2

To find median of n elements we need O(n ) time

Sort the above created ⌈n/5⌉ groups and find median of all groups. Create an auxiliary array ‘median[]’ and store medians of all ⌈n/5⌉ groups in this median array.

So here we have groups of only 5 elements so time needed is constant i.e O(1)

so In all Step 1 and Step 2 will take O(n) time

Step 3

We recursively call to find median of median

so Time taken = T(n/5)

Step 4

Is normal Partition algorithm that takes O(n) time

Step 5

What is the worst case size of these recursive calls?

The answer is maximum number of elements greater than median (obtained in step 3) or maximum number of elements smaller than median

At least half of the medians found in step 2 are greater than or equal to median. Thus, at least half of the n/5 groups contribute 3 elements that are greater than median, except for the one group that has fewer than 5 elements. Therefore, the number of elements greater than median is at least.

So In the worst case, the function recurs for at most n – (3n/10 – 6) which is 7n/10 + 6 elements.

So time needed is T(7n/10 +6) = T(7n+10)

So total Recurrence Relation is

T(n) = T(n/5) + T(7n/10) + O(n)

Solve this using substitution

T(n)  <= cn/5 + c(7n/10 + 6) + O(n)
     <= cn/5 + 7cn/10 + c + 6c + O(n)
    <= 9cn/10 + 7c + O(n)
    <= cn, 

So we get on solving the recursion relation time complexity as O(n) is worst case

This completes the algorithm with code and time complexity

---