1. Prove that any comparison-based sorting algorithm requires 0.(N log N) compar- isons on average.
2. We are given an array that contains N numbers. We want to determine if there are two numbers whose sum equals a given number K. For instance, if the input is 8, 4, 1, 6, and K is 10, then the answer is yes (4 and 6). A number may be used twice. Do the following:
a. Give an O(N2) algorithm to solve this problem.
b. Give an O(N log N) algorithm to solve this problem. (Hint: Sort the items ?rst. After that is done, you can solve the problem in linear time.)
c. Code both solutions and compare the running times of your algorithms.