6
$\begingroup$

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.

$\endgroup$
2

1 Answer 1

1
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.