Problem
1. Given a sequence S of n elements, on which a total order relation is defined, describe an efficient method for determining whether there are two equal elements in S. What is the running time of your method?
2. Let S be a sequence of n integers. Describe a method for printing out all the pairs of inversions in S in O(n + k) time, where k is the number of such inversions.