Name:________________________________________

1. (1 pt) What is the definition of a comparison based sorting algorithm?
   
   
   
   
   
   
2. (1 pt) What is the lower bound on the worst-case running time for any comparison-based sorting algorithm?
   
   
   
   
   
   
3. (1 pt) Suppose you are to sort n keys, whose values are integers in the range from 1 to n. What is the worst-case running time of counting sort in this situation?
   
   
   
   
   
   
4. (1 pt) In order for bucket sort to have O(n) running time on n keys, what property about the distribution of keys to buckets must hold?
   
   
   
   
   
   
5. (1 pt) What is the recurrence that describes the running time of randomized select?