$(4\%)$ Coru;iderthefunctionMinMaxiCint a$[],$ int i$,$ int n$,$ int &min, int &max$)$

which returns the locations $($in the variables min and max$)$ of the smallest element

and the largest element in the array a$[$i: i$+$n$-$i$].$ Assume that n $>1$ is a power of

$2.$ Also assume that all elements in a$[]$ are distinct.

MinMaxi$($int a$[],$ int i$,$ int n$,$ int &min, int &max$)\{$

min$=$max$=$i;

for $($j$=$i; j a$[$j$])$ min j;

else if $($a$[$max$]<$ a$[$j$])$ max j;

$\}$

What are the best$-$case and the worst$-$case numbers of element$-$element comparisoru;

that are executed by MinMaxi?

$($b$)(6\%)$

Consider another function MinMax$2$ below:

int i$,$ int n$,$ int &min, int &max$)\{$ MinMax$2($int a$[],$

$\}\}$

min$2$; int mini,

int maxi, max$2$;

int mid;

if $($n $==$ i$)$

min $=$ max i;

else if $($n $==2)$

if $($a$[$i$]>$ a$[$i$+$i$])\{$

min $=$ i$+1$; max $=$ i;

$\}$

else $\{$

min i; max i$+1$;

$\}$

else $\{$

MinMax$2($a$,$ i$,$ n$/2,$ mini, maxi$)$;

MinMax$2($a$,$ i$+$n$/2,$ n$/2,$ min$2,$ max$2)$;

if $($a $[$mini$]<$ a $[$min$2])$

min $=$ mini;

else

min $=$ min$2$;

if $($a $[$maxi$]>$ a $[$max$2])$

max $=$ maxi;

else

max $=$ max$2$;