Dynamic Programming Project Task

You are given two sorted lists of integers, A and B, of size n (you may assume all integers are distinct). You wish to find the upper median of the union of the two lists. The median of an odd sized list is defined to be the "middle" element when sorted. Since there are 2n total elements there is no median element. Instead, there are two middle elements the lower median and the upper median. (Sometimes in statistics you are told to average these two medians - we will not do this in this problem.) Let M (A, B) express the upper median of the union of A and B. a) Show how you can use the (upper) medians of the two lists to reduce this problem to its sub-problems. State a precise self-reduction for your problem. b) State a recursive algorithm that solves the problem based on your reduction. c) State a tight asymptotic bound on the number of operations used by your algorithm in the worst case.