Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

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.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips 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.