4. (15 points) What is the best, worst and average running time of quick sort algorithm? (a) Provide recurrence relations. For the average case, you may assume that quick sort partitions the input into two halves proportional to c and 1- c on each iteration. (b) Solve each recurrence relation you provided in part (a) (c) Provide an arrangement of the input array which results in each case. Assume the first item is always chosen as the pivot for each iteration