Question # 1 (Need proper solution)

In the 2-Way-2- Sum decision problem, we are given arrays A and B of length n containing (not necessarily distinct) integers, and we must determine whether there are two pairs of indices i1, j1, i2, j2 {1, 2, . . . , n} (not necessary distinct) for which A[i1] + A[i2] = B[j1] + B[j2]. Design an efficient algorithm that solves the 2-Way-2- Sum problem and has time complexity O(n 2 log n) in the setting where operations on individual integers take constant time. Note, that brute force solution that tries all possible quadruples of indices will have the running time of (n 4 ). Less straightforward solution that reduces the problem to 3- Sum which is described in lecture notes, will have the running time of (n 3 ). So both of these solutions are unacceptable and will receive 0 marks. Your solution must include a description of the algorithm in words, the pseudocode for the algorithm, a justification of its correctness, and an analysis of its time complexity in big- notation.