Question $3.$ Consider the following function.

Input: Array $A$ of at least $j$ elements. Integers i and $j.$

Result: A permutation of the i through $j$ elements of A such that

$A[i]A[i+1]A[i+2]$cdots$A[j].$

Let $n=j-i+1$ be the number of elements being sorted.

Function RandomizedSelect is the function defined in the class and in the slides that

returns the $k\text{'}$th order statistic of $S=\{A[i],A[i+1],$dots,$A[j]\}$ in this case $k=\frac{n+1}{2}.$

Function Partition is the function defined in the class and in the slides that partitions

the array into elements less than $p$ and elements greater than $p.$ You can use the worst case

and expected running time of RandomizedSelect that we have seen in the class.

Assume that all elements of A are distinct.

What's the asymptotic worst case running time of FastSort? Justify your answer.

What's the asymptotic expected running time of FastSort? Justify your answer.