Question

Please show clear explanation for both parts explain how you would use merge sort for (a) and divide and conquer for (b).

Order Statistic. Given two sorted lists x and y. Both x and y have size n.

(a) Describe an algorithm that finds the median of X $\bigcup$ Y in O(n) time.

(b) Describe an algorithm that finds the median of X $\bigcup$ Y in O(logn) time.

Answer 1

(a)

This can be done by the following steps:

1. First use the merge procedure on lists x and y. This takes O(n) time.
2. Now we know that the merged list has 2n number of elements.
3. Since, we have even number of elements, so median = mean of the two middle elements.
4. The middle elements are in position - n and n+1
5. Find the elements at n and n+1. This takes O(n) time because we have to traverse the list once.
6. Average the elements found in previous step. This takes O(1) time because we are averaging 2 elements.
7. The average found in prevoius step is the final answer.

Total time complexity = O(n) + O(n) + O(1) = O(n)

---------------------

(b)

This can be done by repeatedly finding median of each list and comparing them which causes the lists to shrink.

Below are the steps:

1. Find median of list1 and list2 as m1 and m2.
2. Compare m1 with m2
3. If m1 = m2, then return one of those.
4. If m1 > m2
   • median must be between first element of list1 to m1, OR
   • from m2 to last element of list2
   • Shrink the lists appropriately. This will get rid of half of the elements.
5. Similarly, process the lists if m2 > m1
6. This is done till size of each list is 2.
   • Required median = maximum(list1[0], list2[0]) + maximum(list1[1], list2[1])/2

Since at each each recursive call, the size of elements is halved, therefore, time complexity is O(log n).

If you have any query, ask in the comment section. If helpful, click on the thumbs up button.