ordering of two keys our goal is to solve the problem using the minimum number of comparisons given this definition for searchingwe can easily come up with the standard sequential search algorithmand we can also see that the lower bound for this problem is "obviouslyn comparisons (keep in mind that the key might not actually appear in the list howeverlower bounds proofs are bit slipperyand it is instructive to see how they can go wrong theorem the lower bound for the problem of searching in an unsorted list is comparisons here is our first attempt at proving the theorem proofwe will try proof by contradiction assume an algorithm exists that requires only (or lesscomparisons of with elements of because there are elements of la must have avoided comparing with [ifor some value we can feed the algorithm an input with in position such an input is legal in our modelso the algorithm is incorrect is this proof correctunfortunately no first of allany given algorithm need not necessarily consistently skip any given position in its searches for exampleit is not necessary that all algorithms search the list from left to right it is not even necessary that all algorithms search the same positions first each time through the list we can try to dress up the proof as followson any given run of the algorithmsome element position (call it position igets skipped it is possible that is in position at that timeand will not be found unfortunatelythere is another error that needs to be fixed it is not true that all algorithms for solving the problem must work by comparing elements of against an algorithm might make useful progress by comparing elements of against each other for exampleif we compare two elements of lthen compare the greater against and find that it is less than kwe know that the other element is also less than it seems intuitively obvious that such comparisons won' actually lead to faster algorithmbut how do we know for surewe somehow need to generalize the proof to account for this approach we will now present useful technique for expressing the state of knowledge for the value relationships among set of objects total order defines relationships within collection of objects such that for every pair of objectsone is greater than the other partially ordered set or poset is set on which only partial order is defined that isthere can be pairs of elements for which we cannot decide which is "greaterfor our purpose herethe partial order is the state of our