In all the algorithms, always explain (more precisely try to prove) the correctness of your algorithm. You Always Must analyze the running time of any algorithm. The time complexity should be as small as possible. Do EVEN THINK OF WRITING PROGRAMS.

Q1: Let A and B be two sorted arrays of n elements each (thus A + B has 2 n elements in total). Give an algorithm that finds the median of A B. This is a number that is larger equal than half the elements and is strictly smaller than half of the elements.

Remark: For simplicity assume that every value appears at most once in A B.

Example: A =< 2, 7, 19, 22 > B =< 6, 17, 24, 25 >

The number 17 is at least as large as < 2, 6, 7, 17 > and smaller than < 19, 22, 24, 25 >