Answer all parts including part 3!!

2.4 CHALLENGE Consider the following observation on the randomized Quicksort algorithm. Because the pivot is chosen uniformly at random among the n input element, with probability the chosen pivot's position on the sorted list will be between and 3n (i.e. a good pivot), and with probability the chosen pivot's position on the sorted list will be between 1 and or between on and n (i.e. a bad pivot). (1 point) 1. State a recurrence that expresses the worst case for bad pivots. (1 point) 2. State another recurrence that expresses the worst case for good pivots. (3 points) 3. Prove by induction that a suitable combination of the two recurrences above expressing the expected worst case for any pivot is (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, lack of clarity, or incomplete proofs. 2.4 CHALLENGE Consider the following observation on the randomized Quicksort algorithm. Because the pivot is chosen uniformly at random among the n input element, with probability the chosen pivot's position on the sorted list will be between and 3n (i.e. a good pivot), and with probability the chosen pivot's position on the sorted list will be between 1 and or between on and n (i.e. a bad pivot). (1 point) 1. State a recurrence that expresses the worst case for bad pivots. (1 point) 2. State another recurrence that expresses the worst case for good pivots. (3 points) 3. Prove by induction that a suitable combination of the two recurrences above expressing the expected worst case for any pivot is (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, lack of clarity, or incomplete proofs