1.Prove that it is impossible to develop a comparison-based implementation of the Priority Queue ADT in which both insert and removeMin methods guarantee to use O(log log n ) comparisons in the worst case.
2.[sorting]Suppose that we are given a sequence S of n elements, each of which is an integer in the range [0,n^2-1]. Describe a simple algorithm to sort S in O(n) time.
3. [Hashing] Show that the expected search time for hashing using open addressing is at most 1/(1- w) where w is the load factor. State your assumption.