chap lower bounds figure illustration of using poset to model our current knowledge of the relationships among collection of objects directed acyclic graph (dagis used to draw the poset (assume all edges are directed downwardin this exampleour knowledge is such that we don' know how or relate to any of the other objects howeverwe know that both and are greater than and furtherwe know that is greater than dand that is greater than current knowledge about the objectssuch that zero or more of the order relations between pairs of elements are known we can represent this knowledge by drawing directed acyclic graphs (dagsshowing the known relationshipsas illustrated by figure initiallywe know nothing about the relative order of the elements in lor their relationship to so initiallywe can view the elements in as being in separate partial orders any comparison between two elements in can affect the structure of the partial orders this is somewhat similar to the union/find algorithm implemented using parent pointer treesdescribed in section nowevery comparison between elements in can at best combine two of the partial orders together any comparison between and an elementsay ain can at best eliminate the partial order that contains thusif we spend comparisons comparing elements in we have at least partial orders every such partial order needs at least one comparison against to make sure that is not somewhere in that partial order thusany algorithm must make at least comparisons in the worst case searching in sorted lists we will now assume that list is sorted in this caseis linear search still optimalclearly nobut why notbecause we have additional information to work with that we do not have when the list is unsorted we know that the standard binary search algorithm has worst case cost of (log ncan we do better than thiswe can prove that this is the best possible in the worst case with proof similar to that used to show the lower bound on sorting again we use the decision tree to model our algorithm unlike when searching an unsorted listcomparisons between elements of tell us nothing new about their