Suppose we are given two sorted arrays (nondecreasing from index 1 to index n) X[1] ... X[n] and Y [1] ... Y[n] of integers. For simplicity, assume that n is a power of 2 (but, it is not needed in general). Problem is to design an algorithm that determines if there is a number p in X and a number q in Y such that p+q is zero. If such numbers exist, the algorithm returns true; otherwise, it returns false. We can consider every pair of numbers, one taken from X and other from Y, using a double-nested loop and solve this in O(na) time. We want to design a better algorithm using divide and conquer (even faster algorithms than the ones proposed here are possible, but the homework is about divide and conquer). (1) Let (X, Y) refer to the given problem. Let T(n) be the complexity of your algorithm when each of X, Y has n elements. Consider each of X, Y divided into two equal halves as shown below: X = X1 X2 Y = Y Y If such a pair p, q of numbers existed, then p has to be in one of X1, X2, and q has to be in one of Y, Y2. Thus, we can determine the answer to problem (X, Y) from answers to the following four smaller problems of half the size: (X1, Y1), (X1, Y2), (X2, Y), and (X2, Y2). (a) (5 pts) Suppose we solve all the four smaller problems (recursively, until we find a p and q such that p+q is zero or we are left with problems of size one which we can solve directly). Do you think this approach will give an algorithm with better complexity than O(n)? Justify your answer by appropriately modeling T(n). There is no need to provide any algorithm.