How to find min and max of 100 numbers ?

[22990atinesh]

Homework Statement

The minimum number of comparisons required to find the minimum and the maximum of 100
numbers is ...

Homework Equations

$T(n)=T(\lceil \frac{n}{2} \rceil) + T(\lfloor \frac{n}{2} \rfloor) + 2$

The Attempt at a Solution

Recurrence for the above problem is
$T(n)=T(\lceil \frac{n}{2} \rceil) + T(\lfloor \frac{n}{2} \rfloor) + 2 \approx 1.5 \times n - 2$

hence $T(100)=1.5 \times 100 - 2 = 148$
But by solving like this I'm coming up with the ans 162

We can divide list of 100 numbers in two list (50,50). Now upon combining the result of these two list 2 more comparisons will be required. Now recursively we break the lists like below, which will make a binary tree

$100 \implies (50,50)$
$50 \implies (25,25)$
$25 \implies (12,13)$
$12 \implies (6,6), 13 \implies (6,7)$
$6 \implies (3,3), 7 \implies(3,4)$
$3 \implies (2,1), 4 \implies (2,2)$

By combining the results upwards in the tree with 2 comparisons on merging each two lists I'm coming up with ans 162 what am I overcounting.

 

[rcgldr]

Splitting up the lists as you've shown, I also get 162. You can either split up the lists into powers of two, or use an iterative approach for 148 compares. In this case, it should be easy to see why the number of compares is ⌈(3n/2)⌉ - 2: the first pair takes 1 compare, all of the remaining pairs take 3 compares, and if there are a odd number of elements, the last one takes 2 compares.

static size_t cmp;              // number of compares

MINMAX findminmax(int a[], size_t sizea)
{
MINMAX minmax;
size_t i;
int min;
int max;

    if(sizea == 0){             // if empty array
        minmax.min = 0;         //   set min = max = 0
        minmax.max = 0;
        return minmax;
    }
    if(sizea == 1){             // if size == 1
        minmax.min = a[0];      //   set min = max = a[0]
        minmax.max = a[0];
        return minmax;
    }
    if(a[0] <= a[1]){           // set initial min and max
        minmax.min = a[0];
        minmax.max = a[1];
    } else {
        minmax.min = a[1];
        minmax.max = a[0];
    }
    cmp += 1;
    for(i = 2; i < (sizea-1); i += 2){ // find min and max
        if(a[i] <= a[i+1]){
            if(a[i  ] < minmax.min)
                minmax.min = a[i  ];
            if(a[i+1] > minmax.max)
                minmax.max = a[i+1];
        } else {
            if(a[i  ] > minmax.max)
                minmax.max = a[i  ];
            if(a[i+1] < minmax.min)
                minmax.min = a[i+1];
        }
        cmp += 3;
    }
    if(i < sizea){
        if(a[i] < minmax.min)
            minmax.min = a[i];
        if(a[i] > minmax.max)
            minmax.max = a[i];
        cmp += 2;
    }
    return minmax;
}