I wrote k-(k/2) instead of k/2 in the second line below because I did not want to have to think about even/odd special cases, nor did I want to worry about which way integer division truncates. I know for certain that a path k/2 steps long (leading to r) followed by a path k-(k/2) steps long is going to be k steps long, and that's all that matters. Still, let's see what happens with some small even and odd numbers. Suppose, for example, that k is 7, which would be the longest possible path through a set of 8 points. Then we would be looking for a path 3 steps long to r, followed by a path 7-3, or 4, steps long from r to q. If k were 6, then we would be looking for 3 steps followed by 3 more steps, which again would give us a path of the right length.

Our algorithm then defines path(p, q, k) as follows:

• If k==0, the result is true if p==q and false otherwise.
• If k==1, the result is true if path(p, q, 0) is true or p is connected directly to q. Otherwise, the result is false.
• If k>1,
  • Look at every element r of the set.
  • If path(p, r, k/2) and path(p, r, k-(k/2)) are both true, the result is true. Otherwise, keep looking.
  • If we have looked at every element of the set and not found one that works, the result is false.

It should be clear that this algorithm works, and that it meets our space requirement. I'm going to leave it as an exercise to figure out how long it takes to run. I think that "horrendous" is a charitable way to describe it.

Because this algorithm is so slow, I don't actually expect anyone to use it. What I want readers to realize is

• Optimization is not always a synonym for "making a program run faster." Sometimes other aspects of a program's execution, particularly space, need attention.
• It is sometimes possible to achieve surprising changes in a program's behavior — and sometimes at surprising cost.
• Dividing a problem in half and solving the halves recursively uses only log(n) levels of recursion.