- #1

- 142

- 1

## 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.