Correct Option: C
The answer is a stub!
Tournament Method:
- Imagine using merge sort and you’d divided the array elements in pairs of two, every element is compared with each other.
- The largest(or smallest if preferred) is selected out each pairs and the winners are copied to a new array and the procedure it repeated till we have one element remaining.
For this,
At first we need $\frac{n}{2}$ comparisons(since $\frac{n}{2}$ pairs), then $\frac{n}{4}$, so on this sums to $n$ , an AP problem.
$\text{Comparisons Req. for finding the Max Element}=\cfrac{n}{2}+\cfrac{n}{4}+\cfrac{n}{8}...=n$
- For finding the smallest element we would use the losers left out in the first round $\frac{n}{2}$ losers to be precise.
- We again use this procedure with an intention for finding smaller amongst all, (worst losers will be the best winners in these rounds, ironical indeed).
For this,
We need, $\frac{n}{4}$ at first since we are pitting losers against losers comparisons then, $\frac{n}{8}$ so on which sums upto $\frac{n}{2}$.
$\text{Comparisons Req. for finding the Min Element}=\cfrac{n}{4}+\cfrac{n}{8}+\cfrac{n}{16}...=\cfrac{n}{2}$
$\text{Total Number of Comparisons Number Required}=n+\cfrac{n}{2}=\cfrac{3n}{2}$
The number of comparisons needed is at least $\cfrac{3}{2}n$ if we consider the elements to be distinct.
Hence C is the answer.
Another more intuitive way to understand this is the build heap operation. I’ll leave that to you...