Question
1. Prove that it is impossible to extend 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. Assume that we are given a sequence S of n elements, each of which is an integer in the range [0,n^2-1]. Explain a simple algorithm to sort S in O(n) time.
3. demonstrate that the expected search time for hashing using open addressing is at most 1/(1- w) where w is the load factor. State your supposition.