2.4 CHALLENGE In lecture we considered a proof that the expected worst case running time of the randomized quicksort algorithm is (n log n). The analysis used an integral approximation for a summation that we have not studied in this class. There is a proof of this result that does not rely on this method. The proof is based on the following observation. With probability the pivot selected will be between and (i.e. a good pivot). Also with probability the pivot selected will be between 1 and or between 3n and n (i.e. a bad pivot). (1 points) 1. State a recurrence that expresses the worst case for bad pivots. (1 points) 2. State a recurrence that expresses the worst case for good pivots. 2 points) 3. State a recurrence that expresses the expected worst case by combining the first two recurrences (6 points) 4. Prove by induction that your recurrence is in O(nlogn). Grading Correctness and precision are of utmost importance. Use formal proof structure for the big-Theta bounds. You will be docked points for errors in your math, disorganization, unclarity, or incomplete proofs