"Consider the following problem: we are given a table of n integer keys A1 , A2 , ..., An and a query integer
X. We want to locate X in the table, but we are in no particular hurry to succeed; in fact, we would like
to delay success as much as possible."
"Of course, we can get very slow algorithms by adding spurious loops before the first test of X against
the A i . However, such easy solutions are unacceptable because any fool can see that the algorithm is just
wasting time. Therefore, 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."
"This represents a disimprovement by a factor of n over the näive algorithm. Observe that the lack of
enthusiasm of the reluctant search algorithm is not at all evident from its behavior since it performs a
X = A i test every O(1) operations, never repeats a test, and stops as soon as it finds the answer. Few
search algorithms, honest or not, can match this performance."
"Reluctant algorithms have plenty of important practical applications. For example, the reluctant search
algorithm is particularly applicable to the case of real keys (real not in the mathematical sense, but rather
in the sense that they can be used to open doors and drawers). The reluctant search algorithm is the only
one known so far that accurately emulates the behavior of bundles of such keys."
"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."
"The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps
the single most important paradigm in the development of reluctant algorithms. The basic multiply and
surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly
simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this
fashion as long as possible. At some point the subproblems will all become so simple that their solution
can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the
time this point is reached the total work will be substantially higher than what could have been wasted
by a more direct approach."
"For practical applications, it is obvious that slowsort is the eminently suitable algorithm whenever your
boss sends you to sort something in Paris. Among other nice properties, during the execution of slowsort
the number of inversions in A is nonincreasing. So, in a certain sense (if you are in Paris, all expenses
paid, this sense is clear) slowsort never makes a wrong move."