Algorithm quick-sort compared to insertion-sort

We say that an array A is c-nice for a constant c if for all 1-i c, we have that AM AU]. For example, a 1-nice array is completely sorted (in ascending order). In this problem we will sort such c-nice arrays A using INSERTIONSORT and QUICKSORT and compare the results. a) (4 Points) In asymptotic notation (remember that c is a constant) what is the worst-case running time of INSERTIONSORT on a 0-nice array? Consider now a run of QUICKSORT on a c-nice array (where the pivot element is chosen (determin- istically) as the last element of the array) (b) (2 points) Derive a lower bound on the rank q of the pivot. 'Among n elements, the ith smallest element has rank i PS 4, Page 2 (c) (3 points) Argue that after partitioning, the two subarrays A[11-1] and Ale+ 1 . . . n] to the left and to the right of the pivot, respectively, are both c-nice. d) (4 points) From the lecture you already know that the running time of quicksort on sorted arrays is e(n2). Let B(n) denote the best-case running time of QUICKSORT on c-nice array with n elements. Using your results from (b) and (c), derive a recurrence for B(n) and solve it (e) (1 point) Asymptotically, which is faster on c-nice arrays: the worst-case running time of insertion sort or the best-case running time of quicksort