3. (40 marks) Let X and Y be two arrays, each containing n distinct integers in ascending order. The problem is to compute the median of all 2n elements in time (lg n) (a) (5 marks) Give a formal definition (pre- and post-conditions) of the problem described. (b) (10 marks) Give a divide-and-conquer algorithm for solving the problem. (c) (10 marks) Prove that your algorithm is correct (d) (5 marks) Express the run-time of your algorithm as a recurrence relation. Explain why your recurrence relation is correct (e) (10 marks) Prove a tight asymptotic bound on the run-time of your algorithm (proving upper and lower bounds separately if necessary). You may use the master theorem, or a version of the "guess and prove" method. Note: Algorithms that do not use divide-and-conquer will receive no credit. Divide-and- conquer algorithms with run-time in (Ign) will receive partial credit