Question

Find the median (middle value) of an array of numbers, which we will assume are all distinct. For example, if there are 27 elements, then you must return the 14th smallest (which is also the 14th largest). The strategy used to solve this problem is somewhat like the quicksort algorithm, but has some important differences. Consider choosing a pivot element and partitioning the input so that the elements less than the pivot are to its left, and those larger than the pivot to its right.

(a) Approximately how many comparisons are required to perform this partitioning?

(b) How can we efficiently determine which partition contains the median?

(c) Having answered part (b), describe a recursive algorithm to find the median.

(d) Now assume that you can guarantee that the pivot partitions the input into one part that has at most 3/4 of the elements, and one part that has at least 1/4 of the elements. Write a recurrence relation for the number of comparisons in this algorithm, C(n), assuming the worst partition, subject to the guarantee.

(e) Solve this recurrence relation, assuming C(1)=0. What do you conclude about the running time required to find the median element?

(f) How can choosing the pivot element uniformly at random help you to obtain the guarantee mentioned in part (d)?

Answer 1

a) In worst case we will require around N² comparisons as partition function i.e. finding pivot element takes O(N) time and there can be O(N) pivot elements

Each pivot element takes O( N ) time so

No of comparisons = O (N) * O(N) = O(N²) = N²

b) We will apply partition algorithm and arrange all the elements smaller than the pivot on its left and the elements greater than it on its right.

Lets say pos of pivot is P .

Now the position of the chosen pivot is the middle of the array then it is the required median of the given array.

Let k = middle element of array  

and We are currently at Partition from L to R

If P >= k then find the index in first half of array

i,e apply partition algo on arr( L to P)

If P < K  then find the index in second half of array

i,e apply partition algo on arr( P to R)

c)

Algorithm

1. Randomly pick pivot element from arrray and the using the partition step from the quick sort algorithm arrange all the elements smaller than the pivot on its left and the elements greater than it on its right.

2. If after the previous step, the position of the chosen pivot is the middle of the array then it is the required median of the given array.

3. If the position is before the middle element then repeat the step for the subarray starting from previous starting index and the chosen pivot as the ending index.

4. If the position is after the middle element then repeat the step for the subarray starting from the chosen pivot and ending at the previous ending index.

5. In case of even number of elements, the middle two elements have to be found and their average will be the median of the array.

6. Repeat Step 3 or 4 until you find the median of array

d) Recurrence Relation

C(n) = C(n/4) + C(3n/4) + cn

here c is a constant

Note This Recurrence relation represents average time complexity of Quicksort Algorithm

e)

C(1) = 0

For Convenience lets denote C using T

T(n) = T(n/4) + T (3n/4) + cn here c is a constant

Drawing recurrence tree of above recurrence relation :

it takes log_4/3N levels to get down to a subproblem of size 1.

Since each right child is 3/4 of the size of the node above it (its parent node), each parent is 4/3 times the size of its right child.

So from subproblem of size 1 we will multiply the size by 4/3 until we reach n.

Now for For what value of X (4/3)^x = n

Taking log with base 4/3 to both sides  

we will get x = log_4/3n .

there are log_4/3n levels each level have partitioning time at most cn

So overall Time complexity = O(nlog_4/3n)

This is concluded time complexity of finding the median.

f) We if choose pivot element uniformly and randomly then pivot element always occur in middle part of the array.

This can be showed by the below image

So choosing pivot element uniformly randomly will guarantee atmost 3/4 elements at one side  and 1/4 elements at other side.