Le second maximum et son compte de comparaisons

On organise les éléments sous forme d'arbre de tournoi (comme dans une phase finale de compétition).

1. On compare les éléments deux à deux. Les vainqueurs passent au tour suivant. Il faut exactement $n-1$ comparaisons pour désigner le maximum global (le champion).
2. Le second maximum fait nécessairement partie des éléments qui ont été directement battus par le maximum global (s'il avait été battu par un autre, cet autre aurait été battu par le maximum global ou éliminé plus tôt).
3. Le champion ayant disputé exactement $\lceil {\log }_{2}n\rceil$ matchs, il a fait face à $\lceil {\log }_{2}n\rceil$ victimes.
4. Il suffit de chercher le maximum parmi ces victimes, ce qui demande $\lceil {\log }_{2}n\rceil -1$ comparaisons supplémentaires. Le nombre total de comparaisons est $n+\lceil {\log }_{2}n\rceil -2=O(n)$, ce qui est bien inférieur à $2n-3$ pour de grandes valeurs de $n$.