I just need help except part a

4. Quicksort (20 points). In practice, quicksort is one of the fastest sorting algorithms. 1. Pick a pivot (e.g. the first element) bee bed cab ace dad baa add ebb 2. Reorder the array such that all elements pivot are to its right. add bed ace baa bee cab dad ebb left_partition right partition 3. Recursively sort each partition. void qsort (vector & x, int lo, int hi) { if (lo >= hi) return; int p = lo; for(int i=lo+1; i & x) { qsort(x, 0, x.size()-1); (a) (4 points) Show the contents of the array x at the start of each iteration of the for-loop, after the for-loop, and after the swap, in the call qsort(x, 0, 3) on the input shown below: lo=0 1 2 hi=3 4 5 6 7 start of iter i =1 add bed ace baa bee cabdad ebb start of iter i = 2 bee cabdad ebb start of iter i = 3 bee cabdad ebb end of iter i = 3 bee cab dad ebb after swap(x[lo],x[p])| bee cab dad ebb (b) (4 points) Complete the following loop invariant by providing the range of indices for which the statement is true. Note that x[ a ... b] is empty if a > b. At the start of iteration i of the for-loop in qsort: (A) x[ - ]= x[lo], which part of the invariant at iteration i +1 is the same as at iteration i, (A) or (B)? (d) (4 points) What is the worst case running time of Quicksort on inputs of size n? First, show the recurrence relation representing the running time for a worst case input. Then give the asymptotic result. (e) (4 points) Suppose in every recursive call to sort a subarray, we choose a pivot, in time proportional to the size of the subarrary, that is never one of the smallest 1/4 or largest 1/4 elements. What is the worst case running time of Quicksort on inputs of size n in this case? Give the recurrence and the asymptotic closed form. 4. Quicksort (20 points). In practice, quicksort is one of the fastest sorting algorithms. 1. Pick a pivot (e.g. the first element) bee bed cab ace dad baa add ebb 2. Reorder the array such that all elements pivot are to its right. add bed ace baa bee cab dad ebb left_partition right partition 3. Recursively sort each partition. void qsort (vector & x, int lo, int hi) { if (lo >= hi) return; int p = lo; for(int i=lo+1; i & x) { qsort(x, 0, x.size()-1); (a) (4 points) Show the contents of the array x at the start of each iteration of the for-loop, after the for-loop, and after the swap, in the call qsort(x, 0, 3) on the input shown below: lo=0 1 2 hi=3 4 5 6 7 start of iter i =1 add bed ace baa bee cabdad ebb start of iter i = 2 bee cabdad ebb start of iter i = 3 bee cabdad ebb end of iter i = 3 bee cab dad ebb after swap(x[lo],x[p])| bee cab dad ebb (b) (4 points) Complete the following loop invariant by providing the range of indices for which the statement is true. Note that x[ a ... b] is empty if a > b. At the start of iteration i of the for-loop in qsort: (A) x[ - ]= x[lo], which part of the invariant at iteration i +1 is the same as at iteration i, (A) or (B)? (d) (4 points) What is the worst case running time of Quicksort on inputs of size n? First, show the recurrence relation representing the running time for a worst case input. Then give the asymptotic result. (e) (4 points) Suppose in every recursive call to sort a subarray, we choose a pivot, in time proportional to the size of the subarrary, that is never one of the smallest 1/4 or largest 1/4 elements. What is the worst case running time of Quicksort on inputs of size n in this case? Give the recurrence and the asymptotic closed form