Question $5$

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

Algorithm $1$ Quicksort algorithm

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

if r $$ l $+1<=1$ then

return

end

p $$ 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$)$:

i $$ l $+1$

for j $$ l $+1$ to r do

if A$[$j$]<=$ p then

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

i $$ i $+1$

end

end

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

return i $1$

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

return A$[($l $+$ r$)/2]$ Calculate a tight bound for this recurrence using the iteration method.