stop trying to find an (asymptoticallyfaster algorithm what if the (knownupper bound for our algorithm does not match the (knownlower bound for the problemin this casewe might not know what to do is our upper bound flawedand the algorithm is really faster than we can proveis our lower bound weakand the true lower bound for the problem is greateror is our algorithm simply not the bestnow we know precisely what we are aiming for when designing an algorithmwe want to find an algorithm who' upper bound matches the lower bound of the problem putting together all that we know so far about algorithmswe can organize our thinking into the following "algorithm for designing algorithms " if the upper and lower bounds matchthen stopelse if the bounds are close or the problem isn' importantthen stopelse if the problem definition focuses on the wrong thingthen restate itelse if the algorithm is too slowthen find faster algorithmelse if lower bound is too weakthen generate stronger bound we can repeat this process until we are satisfied or exhausted this brings us smack up against one of the toughest tasks in analysis lower bounds proofs are notoriously difficult to construct the problem is coming up with arguments that truly cover all of the things that any algorithm possibly could do the most common fallacy is to argue from the point of view of what some good algorithm actually does doand claim that any algorithm must do the same this simply is not trueand any lower bounds proof that refers to specific behavior that must take place should be viewed with some suspicion let us consider the towers of hanoi problem again recall from section that our basic algorithm is to move disks (recursivelyto the middle polemove the bottom disk to the third poleand then move - disks (again recursivelyfrom the middle to the third pole this algorithm generates the recurrence ( ( sothe upper bound for our algorithm is but is this the best algorithm for the problemwhat is the lower bound for the problemfor our first try at lower bounds proofthe "triviallower bound is that we must move every disk at least oncefor minimum cost of slightly better is to this is minor reformulation of the "algorithmgiven by gregory rawlins in his book "compared to what?