chap lower bounds observe that to get the bottom disk to the third polewe must move every other disk at least twice (once to get them off the bottom diskand once to get them over to the third polethis yields cost of which still is not good match for our algorithm is the problem in the algorithm or in the lower boundwe can get to the correct lower bound by the following reasoningto move the biggest disk from first to the last polewe must first have all of the other disks out of the wayand the only way to do that is to move them all to the middle pole (for cost of at least ( )we then must move the bottom disk (for cost of at least oneafter thatwe must move the remaining disks from the middle pole to the third pole (for cost of at least ( )thusno possible algorithm can solve the problem in less than steps thusour algorithm is optimal of coursethere are variations to given problem changes in the problem definition might or might not lead to changes in the lower bound two possible changes to the standard towers of hanoi problem arenot all disks need to start on the first pole multiple disks can be moved at one time the first variation does not change the lower bound (at least not asymptoticallythe second one does lower bounds on searching lists in section we presented an important lower bounds proof to show that the problem of sorting is th( log nin the worst case in we discussed number of algorithms to search in sorted and unsorted listsbut we did not provide any lower bounds proofs to this important problem we will extend our pool of techniques for lower bounds proofs in this section by studying lower bounds for searching unsorted and sorted lists searching in unsorted lists given an (unsortedlist of elements and search key kwe seek to identify one element in which has key value kif any exist for the rest of this discussionwe will assume that the key values for the elements in are uniquethat the set of all possible keys is totally ordered (that isthe operations are defined for all pairs of key values)and that comparison is our only way to find the relative recalling the advice to be suspicious of any lower bounds proof that argues given behavior "musthappenthis proof should be raising red flags howeverin this particular case the problem is so constrained that there really is no (betteralternative to this particular sequence of events