3.In this question, we consider the expected running time of the QuickSort algorithm when the pivot is chosen randomly. (If you do not know what QuickSort is, part of your job is to look it up from the internet and self-learn the algorithm.) (a) (25 points) Show that it runs in O(n^c) 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) (5 bonus points) Show that it runs in O(n log n) time on average.