I have two questions. Both are about finding any of the 3 largest among $n$ elements.How to show that $n-3$ comparisons suffice to find any of the $3$ largest among $n$ given numbers $(n \geq 4)$?How to show that $n-3$ comparisons are necessary to find any of the $3$ largest among $n$ given numbers $(n \geq 6)$?My Idea: I have tried to solve 1. using a heap but could not derive any such bound.The place where I found this question gave one hint which said to analyze the number of connected components in a comparison graph. I shall appreciate if anyone can throw some light on a comparison graph.
Find any of the 3 largest among $n$ elements
algorithms