How many comparisons do we need to find min and max of n numbers?

Problem Detail: 

Suppose we have given a list of 100 numbers. Then How can we calculate the minimum number of comparisons required to find the minimum and the maximum of 100 numbers.

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 as I've mentioned below, 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 over counting.

Asked By : Atinesh

Answered By : Andreas Schmelz

You're dividing badly. If you look at your execution tree, you'll notice that most of the leaves on the last level are 3's. This means you'll need 3 comparisons here. For the same cost you could also compare 4 elements. Your efficiency here is 75%.

Your partial trees have to be full to be the most efficient. So you'll need to divide into trees with numbers of elements that are powers of two.

In your case dividing into a left oriented tree it's

T(100) = T(64) + T(36) +2        = T(64) + T(32) + T(4) + 4        = 94 + 46 + 4 + 4        = 148 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35321