1.[Sorting: ] Please prove that any comparison-based sorting algorithm requires O(n Ign) computation time in the worst case, where n is the number of objects to be sorted.

(3) What is the assumption of simple uniform hashing? Under this assumption, given a hash table with m slots that stores n elements, what is the expected time taken by an unsuccessful search when the hash collisions are resolved by chaining?