Consider the following implementation of Quick sort.

static int partition$($int$[]$ numbers, int i$,$ int k$)\{$

int pivot $=$ numbers$[$i$],$ l $=$ i$,$ h $=$ k;

while $($true$)\{$

while $($numbers$[$l$]<$ pivot$)\{$

$++$l;

$\}$

while $($pivot $<$ numbers$[$h$])\{$

$--$h;

$\}$

if $($l $>=$ h$)\{$

return h;

$\}$

else $\{$

swap$($numbers$,$ l$,$ h$)$;

$++$l;

$--$h;

$\}$

$\}$

$\}$

static void qsort$($int$[]$ arr, int l$,$ int h$)\{$

if $($l $>=$ h$)\{$

return;

$\}$

int j $=$ partition$($arr$,$ l$,$ h$)$;

qsort$($arr$,$ l$,$ j$)$;

qsort$($arr$,$ j $+1,$ h$)$;

$\}$

static void swap$($int$[]$ arr, int i$,$ int j$)\{$

int temp $=$ arr$[$i$]$;

arr$[$i$]=$ arr$[$j$]$;

arr$[$j$]=$ temp;

$\}$

The above implementation should compile and run, e$.$g$.,$

int arr$[]=\{3,14,1,5,9,26\}$;

qsort$($arr$,0,$ arr.length $-1)$;

$($a$)$Let h $$ l $+1=$ N and assume numbers is comprised of N $>0$ distinct

elements in ascending order. Let C$($N $)$ denote the number of comparisons involving

elements of numbers performed by partition$($numbers$,$ l$,$ h$).$

What is C$($N $)?$

Note that inside partition$(),$ i is initialized with the value of l and k is initialized

with the value of h$.$

$($b$)$ Assume numbers is comprised of N $>0$ distinct elements in ascending

order. Let T $($N $)$ denote the number of comparisons involving elements of numbers

performed by qsort$($numbers$,0,$ numbers.length $-1).$

Give the full recurrence for T $($N $),$ which must explicitly use C$($N $)$ from the previous

part.

Justify every aspect of your recurrence.

$($c$)$ Solve the recurrence you gave for T $($N $)$ from the previous part to get a

closed form expression for T $($N $).$ Justify your solution through iteration or induc$-$

tion. State your closed form expression in terms of $.$

$($d$)$ Discuss whether qsort$()$ is optimal, e$.$g$.,$ is qsort$()$ optimal? Why or

why not? You must use your answers to the previous parts in your discussion.