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. 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(n 2 ) time (a faster algorithm than the ones proposed here exists, but the homework is about divide and conquer). (1) We want to design a better algorithm using divide and conquer. 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 = Y1 Y2 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 Y1, 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, Y1), and (X2, Y2).

(e) (5 pts) Model T(n), the complexity of your algorithm when invoked as zeroSum (X, 1, n, Y, 1, n), via a recurrence. Find a theta bound for T(n).