Problem #2: [30 ts] {a} Given the following list of numbers: 3, 1, 4, 1, 5, 9, 2, 6, 5r 3, 5 trace the execution for quicksort with median-Dfthree 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} + 2cn; TI[1} = D 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.l] What is the worst-case complexity of 1your improved insertion sort if you take account of only the comparisons made by the binary search? {c2} What is the worst-case complexity of your improved insertion sort if only swapsfinversions of the data values are taken into account