In all the algorithms, always explain their correctness and analyze their complexity. The complexity should be as small as possible. Do not EVER write a program.

Question 1: 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 AUB. This is a number that is larger and equal of half the elements, and is strictly smaller than half of the elements Remark: For simplicity assume that every value appears at most once in AUB Example A 2, 7, 19, 22 > - 6, 17, 24, 25 > The number 17 is at least as large as 2, 6, 7, 17 > and smaller than19, 22, 25, 25 > Hint: There is a very fast algorithm for this task