chap lower bounds for total cost of comparisons is this optimalthat seems doubtfulbut let us now proceed to the step of attempting to prove lower bound theorem the lower bound for finding the second largest value is proofany element that loses to anything other than the maximum cannot be second sothe only candidates for second place are those that lost to the maximum function largest might compare the maximum element to others thuswe might need additional comparisons to find the second largest this proof is wrong it exhibits the necessity fallacy"our algorithm does somethingtherefore all algorithms solving the problem must do the same this leaves us with our best lower bounds argument at the moment being that finding the second largest must cost at least as much as finding the largestor let us take another try at finding better algorithm by adopting strategy of divide and conquer what if we break the list into halvesand run largest on each halfwe can then compare the two winners (we have now used total of comparisons)and remove the winner from its half another call to largest on the winner' half yields its second best final comparison against the winner of the other half gives us the true second place winner the total cost is / is this optimalwhat if we break the list into four piecesthe best would be / what if we break the list into eight piecesthen the cost would be / pushing this idea to its extremethe only candidates for second place are losers to the eventual winnerand our goal is to have as few of these as possible so we need to keep track of the set of elements that have lost in direct comparison to the (eventualwinner we also observe that we learn the most from comparison when both competitors are known to be larger than the same number of other values so we would like to arrange our comparisons to be against "equally strongcompetitors we can do all of this with binomial tree binomial tree of height has nodes either it is single node (if )or else it is two height binomial trees with one tree' root becoming child of the other figure illustrates how binomial tree with eight nodes would be constructed the resulting algorithm is simple in principlebuild the binomial tree for all elementsand then compare the dlog ne children of the root to find second place we could store the binomial tree as an explicit tree structureand easily build it in time linear on the number of comparisons as each comparison requires one link be added because the shape of binomial tree is heavily constrainedwe can also store the binomial tree implicitly in an arraymuch as we do for heap assume that two treeseach with nodesare in the array the first tree is in positions