In this question, we consider the expected running time of the QuickSort algorithm when the pivot is chosen randomly.

(a)

Show that it runs in O(nc) time on average for some constant c < 2. Hint: Try to mimic our analysis for the randomized selection algorithm in the

slides. You need to choose the range of reasonably good pivot wisely here.

(b)

Show that it runs in O(n log n) time on average.