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.
