You are given two integer arrays X and Y . Find all pairs of elements (\( x_i,y_i \)) such that \( x_i\in X \) and \( y_i\in Y \) where \( x_i+y_i = k \).
Time complexity to sort the arrays using any comparison based sorting = \( O(nlogn) \).
Time complexity to find the pair using recursion = \( O(n) \).
\( \therefore \) Overall time complexity = \(O(nlogn) \).
If we have any prior knowledge about the range (if it is not too large) of the elements in the two arrays we can use counting sort or radix sort, instead of any comparison based sorting. In that case the time complexity for sorting will be linear which results an overall linear time performance of the algorithm.