undefined

Finally, 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 1 and 3 (i.e. a good pivot), and with probability the chosen pivot's position on the sorted list will be between 1 and 4 or between and n (i.e. a bad pivot). 11. (bonus: 1 point) State a recurrence that expresses the worst case for bad pivots. 12. (bonus: 1 point) State another recurrence that expresses the worst case for good pivots. 13. (bonus: 3 points) Prove by induction that a suitable combination of the two recurrences above expressing the expected worst case for any pivot is (nlogn). Finally, 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 1 and 3 (i.e. a good pivot), and with probability the chosen pivot's position on the sorted list will be between 1 and 4 or between and n (i.e. a bad pivot). 11. (bonus: 1 point) State a recurrence that expresses the worst case for bad pivots. 12. (bonus: 1 point) State another recurrence that expresses the worst case for good pivots. 13. (bonus: 3 points) Prove by induction that a suitable combination of the two recurrences above expressing the expected worst case for any pivot is (nlogn)