Problem #2: (30 pts). (a) Given the following list of numbers: 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 trace the execution for quicksort with median-of-three partitioning and a cutoff of 3. (b) The processing time of an algorithm is described by the following recurrence equation (c is a positive constant): T(n)3T(n/3) 2cnT(1)0 What is the running time complexity of this algorithm? Justify. (c) You decided to improve insertion sort by using binary search to find the position p where the new insertion should take place. (c.1) what is the worst-case complexity of your improved insertion sort if you take account of only the comparisons made by the binary search? (c.2) What is the worst-case complexity of your improved insertion sort if only swaps/inversions of the data values are taken into account