figure an example of building binomial tree pairs of elements are combined by choosing one of the parents to be the root of the entire tree given two trees of size fourone of the roots is chosen to be the root for the combined tree of eight nodes to the second tree is in positions to + the root of each subtree is in the final array position for that subtree to join two treeswe simply compare the roots of the subtrees if necessaryswap the subtrees so that tree with the the larger root element becomes the second subtree this trades space (only need space for the data valuesno pointersfor time (in the worst caseall of the data swapping might cost ( log )though this does not affect the number of comparisons requiredbecause the binomial tree' root has log childrenand building the tree requires comparisonsthe total number of comparisons required by this algorithm is dlog ne this is clearly better than our previous algorithm but is it optimalwe now go back to trying to improve the lower bounds proof to do thiswe introduce the concept of an adversary the adversary' job is to make an algorithm' cost as high as possible imagine that the adversary keeps list of all possible inputs we view the algorithm as asking the adversary for information about the algorithm' input the adversary may never liebut it is permitted to "rearrangethe input as it sees fit in order to drive the total cost for the algorithm as high as possible in particularwhen the algorithm asks questionthe adversary answers in way that is consistent with at least one remaining input the adversary then crosses out all remaining inputs inconsistent with that answer keep in mind that there is not really an entity within the computer program that is the adversaryand we don' actually modify the program the adversary operates merely as an analysis deviceto help us reason about the program as an example of an adversaryconsider the standard game of hangman player picks word and tells player how many letters the word has player guesses various letters if guesses letter in the wordthen will indicate which position(sin the word have the letter player is permitted to make only so many guesses of letters not in the word before losing