2. (a) Assume you execute quicksort. Assume it turns out that at every other level of recursive calls you partition on the [n/4]th smallest element. At the other levels you partition on a random element. Analyze the average number of comparisons for this execution quicksort. Just get the exact value for the high order term. You do not have to worry about floors and ceilings and can make reasonable simplifying assumptions. (It turns out to not be much harder to keep track of the floors and ceilings, and to take into account that the median is slightly different depending on whether the list size is even or odd. Your analysis can assume you start with a random element and then the [n/4]th smallest element, or vice versa.) You must use the method of writing a recurrence as we did in class. Show your work. HINT: When you write your recurrence, combine the work of pairs of even/odd levels of the recursive calls. (b) How does your answer compare to our approximation of the average case of quicksort, and to the exact average case of quicksort? 2. (a) Assume you execute quicksort. Assume it turns out that at every other level of recursive calls you partition on the [n/4]th smallest element. At the other levels you partition on a random element. Analyze the average number of comparisons for this execution quicksort. Just get the exact value for the high order term. You do not have to worry about floors and ceilings and can make reasonable simplifying assumptions. (It turns out to not be much harder to keep track of the floors and ceilings, and to take into account that the median is slightly different depending on whether the list size is even or odd. Your analysis can assume you start with a random element and then the [n/4]th smallest element, or vice versa.) You must use the method of writing a recurrence as we did in class. Show your work. HINT: When you write your recurrence, combine the work of pairs of even/odd levels of the recursive calls. (b) How does your answer compare to our approximation of the average case of quicksort, and to the exact average case of quicksort