首先我們證明這個下界是可以得到的。對於n個輸入，進行如下操作：

我們將他兩兩配對進行一次比較，每個配對的勝者放入等待佇列；如果出現未配對的數，放入等待佇列；對等待隊列當作新的輸入，跳轉到1，遞迴執行，直到輸入大小為1此時剩下的數為最大數，整個比較過程可以看作一個只有0度和2度節點的勝者樹，葉子節點就是原始的輸入，頭節點就是最後的最大值，每個2度節點都代表一次比較。根據這種只有0度和2度節點樹的特性，內部節點剛好有n-1個，所以獲得最大值需要n-1次操作。現在我們來獲得第二大的數，這個數有一個性質：他一定與最大數比較過，且是所有與最大數比較過的數中的最大數。為了得到第二大的數，我們只需要收集最大數在整棵勝者樹中路徑所有的兄弟節點，並在此呼叫一次最大數演算法，即可得到第二大的數。由於當前勝者樹的形狀，最大數的所有兄弟節點個數不會超過,所以得到第二大數的比較次數不會超過 。因此，我們可以在比較內得到第二大的數。現在我們來證明最少需要次比較才能得到第二大的數。為了得到第二大的數，我們首先需要得到最大的數，然後將所有與最大數比較過的數中找到最大值，即是第二大。為了得到最小比較次數，所有在比較過程中已經輸過的數沒有必要再參加比較。整個選取最大數的過程也是一個勝者樹，這棵樹有2n-1個節點。這棵勝者樹中，任何一條從葉子節點到頭節點的路徑都可能是最大數的比較路徑，最壞情況下，第二大數的候選集合大小為最長路徑長度-1，額外的比較次數為最長路徑長度-2，此時.對於任何一個含有k個節點的二叉樹，其最長路徑至少為，所以勝者樹中最長路徑最短長度為,所以第二大數的候選集合大小在任何情況下都不可能低於。因此獲得第二大數所需比較次數最少為.綜上，獲得第二大數所需比較次數的下界即為。