Part B (I claim no credit for the idea in the following algorithm it

is the result of researching the field to find the same. The best

I could come up with of off my own bat was an algorithm with

an average number of comparisons ~3n/2)

Code:

function FindSmallestAndLargest(a)
//
// a an array containing numerical values
//
// the function returns {smallest,largest} which are the
// smallest and largest values in array a.
//
smallest=inf;
largest=-inf;
n=length(a);
// if list length not even add a dummy element
// to make it so
if !even(n)
a=a|a(n);
n=n+1;
endif
// loop over idx=1, 3, .. n-1
for idx=1 to n-1 step 2
if a(idx)>a(idx+1)
if a(idx)>largest then
largest=a(idx);
endif
if a(idx+1)<smallest then
smallest=a(idx+1);
endif
else
if a(idx+1)>largest then
largest=a(idx+1);
endif
if a(idx)<smallest then
smallest=a(idx);
endif
endif
endfor
return {smallest, largest}
endfunction

This works by first comparing a pair of elements then comparing the larger

with the current largest, and the smaller with the current smallest for a

total of three comparisons for every two elements in the list, ie for 3n/2

comparions for an even length list and 3(n+1)/2 comparisons for an odd

length list (the list having had to be padded with an extra element in this

case to make the length even).

This may be summarise using the ceiling function $\displaystyle \lceil . \rceil$, as:

$\displaystyle

CC=\lceil 3n/2 \rceil

$

Where the ceiling function gives the smallest integer larger than its argument.

RonL