Find any of the 3 largest among $n$ elements

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.

I don't know what do you mean by comparison graph. However, here is my solution for question 1.

Suppose you have a list of $m$ elements, and you want to find the largest element. You can do this with $m-1$ comparisons.

Do you know how to proceed?


You can simply ignore the first two elements in your list. This gives you a new list $L'$ of $n'=n-2$ elements, You can determine the largest element of $L'$ with $n'-1=n-3$ comparisons. This element is one of the three largest.

StackExchange Computer Science Q#3264, answer score: 9