Question: Repeat Exercise for four numbers. Try to design an O(N2 log N) algorithm.
Exercise: An array contains N numbers, and you want to determine whether two of the numbers sum to a given number K. For instance, if the input is 8, 4, 1, 6 and K is 10, the answer is yes (4 and 6). A number may be used twice. Do the following.
a. Give an O(N 2) algorithm to solve this problem.
b. Give an O(N log N) algorithm to solve this problem. (Hint: Sort the items first. After doing so, you can solve the problem in linear time.)
c. Code both solutions and compare the running times of your algorithms.