# Divide and Conquer -- If You're Patient Enough

February 09, 2012

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.

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>