Largest and smallest elements of a list

Question

What is the minimum number of comparisons required to find the largest and smallest elements of an unsorted list of n distinct elements?

What could be the best time complexity for above algorithm?

From minimum number of comparisons I meant to specify the most efficient algorithm, for the worst case.

Answer 1

The optimal algorithm takes 3/2*n comparisons.

It works like this:

5 2 6 7 3 1 10 35 4 6

1. [5] [6]
   
2. [5, 2], [6, 4]
   
3. [5, 2, 6], [6, 4, 35]
   
4. [5, 2, 6, 7], [6, 4, 35, 10]
   
5. [5, 2, 6, 7, 1], [6, 4, 35, 10, 3]
   

On each step (n/2) steps, you compare i-th and n-i-th element and move to table "bigger" and "lower"

After n/2 steps, you know, that minimum is in "lower" table and maximum is in "bigger" table. Findin min and max within these two tables is (n/2) * 2, so you have (3/2) * n

Answer 2

It is N * (3/2).