Question $5$

The pseudo$-$code for Quicksort algorithm is given below.

Algorithm $1$ Quicksort algorithm

Function Quicksort $($array $A,l,r)$:

if $r-l+11$ then

return

end

plarr ChoosePivot $(A,l,r)$

Partition $(A,p,l,r)$

Quicksort $(A,l,p-1$

Quicksort $(A,p+1,r$

Function Partition $(A,p,l,r)$ :

ilarrl$+1$

for jlarrl$+1$ to $r$ do

if $A[j]p$ then

swap $A[i]$ with $A[j]$

ilarri$+1$

end

end

swap $A[i-1]$ with $p$

return $i-1$

Function ChoosePivot $(A,l,r)$ :

return $A[{|}_{{?}_{?}}\frac{l+r}{2_{{?}_{?}}}|]$

$($a$)$ Write down the recurrence for the running time for the case where the algorithm

chooses the median as the pivot at each iteration.