Quantas comparações a ordem de torneio usa para encontrar o segundo maior elemento, o terceiro maior elemento e assim por diante, até o (
)-ésimo maior (ou o segundo menor) elemento?
Passo 1
O método “ordem de torneio” organiza os
elementos numa árvore de competições: cada partida compara dois elementos e o vencedor sobe ao nível seguinte. Após
comparações obtemos o maior elemento. Guardamos, para cada vencedor, a lista dos elementos que ele derrotou ao longo do torneio. Se
for potência de 2, a altura da árvore é
Para generalizar a caso arbitrário de
, trocaremos depois
por
.
Passo 2
Após o torneio inicial (que custou
comparações), o máximo geral
derrotou exatamente
oponentes. Para encontrar o segundo maior
basta achar o máximo entre esses
elementos – isto são mais
comparações. Logo, o total de comparações para obter o segundo maior é
Passo 3
O vencedor dessa mini-disputa pelos perdedores de
é
. Ele próprio derrotou nos
níveis originais exatamente
oponentes (todos, exceto aquele que o venceu). Para achar o terceiro maior
comparamos agora esses
elementos em
novos confrontos. O total até aqui é
Passo 4
Prosseguindo, para cada
, o
-ésimo maior
surge como o campeão dos perdedores de
, que foram
elementos e exigem
comparações.
Passo 5
Somando tudo, o número de comparações para encontrar o
-ésimo maior é
Passo 6
Se
não é potência de 2, basta tomar
e a fórmula continua valendo em termos de limite superior de comparações. Em particular, para
(ou seja, até o segundo menor) temos
Resposta
Para
:
Em geral basta substituir
.