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
