See also this classic of a paper: Pessimal Algorithms and Simplexity Analysis (pdf) <a href="http://www.researchgate.net/profile/Andrei_Broder/publication/2805500_Pessimal_Algorithms_and_Simplexity_Analysis/links/00b7d5187d62f61ee4000000.pdf" rel="nofollow">http://www.researchgate.net/profile/Andrei_Broder/publicatio...</a><p>> Table search can be viewed as a special cast of the following more general problem. We are given a “maze”, i.e. an undirected graph G with n nodes, and an “entry” node u in it. Our task is to find a path from u to a specified “exit” node v, by walking on the maze one edge at a time. [...]<p>> However, suppose the maze is actually quite agreeable, so much so that we wouldn’t mind spending a few extra cycles in the search for v; in fact we vaguely hope, nay, decidedly wish, that the search will take as long as possible, and even though our sense of duty prevents us from giving up the search altogether, we are not that insensitive to the primeval necessities of our human nature, and besides what is wrong with taking a more relaxed attitude to the problem, as long as we do what we are supposed to do, since we have always been told that haste makes waste, and no one needs to be perfect anyway, and so forth. With these assumptions, the problem falls squarely within the domain of our theory.