Correction: In question 6(b) the limits to the integral are from 1 to n

6. We know the best case for Quick Sort occurs when the pivot key always ends up in the middle of the list. Suppose instead it always ends up 1/4 of the way through the list. Assume that partition takes time exactly n. (a) What would the resulting recurrence relation be? T(n) = (b) There is a generalization of the Master Theorem called the Akra-Bazzi method which can solve this. The solution for this recurrence relation is given by: rn) =0(n(1+ [4a Evaluate this expression to get the time complexity. Note: This shouldn't frighten you, it's very straightforward! I'm only including it so that you can see the value in Calculus as applied to CS. Solution