The foundation paper on pessimal algorithms is:
Broder, Andrei and Stolfi, Jorge,
Pessimal Algorithms and Simplexity Analysis,
ACM SIGACT News, Volume 16, Number 3, Fall 1984, pages 16-3.49 through 16-3.53.
They state their objective as: "we must look for an algorithm that does indeed progress steadily towards its stated goal even though it may have very little enthusiasm for (or even a manifest aversion to) actually getting there".
Some algorithms they analyze include:
- reluctant search, which is like binary search, but it looks in the wrong half each time until stumbling over the desired value when it cannot avoid it any longer.
- sloppiest path problems
- the method of feeblest descent
- backward-first search for enumerating all n vertices of a connected graph G.
- slowsort, "a perfect illustration of the multiply and surrender paradigm", which involves spinning off as many subproblems as possible until they are so simple that their solution can no longer be postponed.
Exercise for the reader of this node: compare the simplexity of slowsort with that of generating all the n! permutations of the input sequence until one finds a sequence in ascending order.