# An Extreme Example of Space Optimization

When people talk about optimization, they usually mean making programs run faster. Many ways of doing so, such as caching and precomputing results that will be used more than once, gain time at the expense of extra memory. Today I want to talk about an example that goes in the opposite direction: sacrificing time to gain space.

The example comes from an exam in an algorithms course many years ago. Suppose you have a very large number — say, 2^{n}— of points. Each of those points may or may not be connected to any of the other points. You can determine whether point `p`

is connected to point `q`

by calling a function path(`p, q`

), which will return `true`

or `false`

. If `p`

is connected to `q`

, that says nothing about whether `q`

is connected to `p`

. It might be connected, or it might not. Because there are 2^{n} points, we will assume that all integers are `n`

bits long and unsigned, so that any integer can store the number of any point, but no more than that.

The problem is to write a program that takes two points `q`

, and determines whether there is a path between them — that is, whether there is a sequence of one or more points in which `p`

is the first point, `q`

is the last point, and each point except the last is connected to its successor.

In principle, this problem is not difficult. For example, we can create an array with one element for each point. That element will eventually tell us how many steps it takes to reach the corresponding point from `p`

, or will 0 if we have not yet found a path from `p`

to that point.

We start by finding all the points to which `p`

is connected directly and giving those points the number 1. Then we look at the direct connections from each of those points, giving those points the number 2 unless they are already numbered 1; and so on. Eventually, we will get to a state in which either we have given a number to `q`

, in which case we have found a path; or we go through all of the points without changing anything, in which case no path exists.

The exam question had a sadistic extra wrinkle that ruled out this kind of straightforward solution: The program was not allowed to use more than O(`n`

) space, measured in (`n`

-bit) integers. In other words, the students were not even allowed to use enough memory to store the entire contents of a single path — because a path might have as many as 2^{n} elements, which would take O(2^{n}) space to store.

Can you figure out how to solve this problem? If you can, how fast (and by fast, I really mean slowly — at least in this case) does it run? I'll reveal the answers next week.

## Comments:

2012-02-08T20:14:37

I suppose if we have the answer, we shouldn't post it?

Permalink

2012-02-03T22:36:44

Isn't directed graph connectivity NL-complete (so you need O(n^2) space to calculate it)?

Permalink

2012-02-03T12:03:48

> 2n elements, which would take O(2^n) space to store.

I think this should be O(2^n * n).

> solve this problem

The O(n) really is a hard constraint as it rules out recursion, due to stack space limitations.

I think there is one interesting "solution" which respects O(n) memory, but has possibly the worst run-time:

Start with p and test whether a connection exists to a randomly chosen point. If "yes", take this point as new reference and iterate. If we happen to meet "q" by the way we're done.

If "no", restart from the very beginning.

Depending on "how reliable" our answer shall be, we can throw in sufficient amount of time. In other words, if we allow an infinite amount of time, we'll get the 100% reliable answer whether a path exists.

Therefore runtime will be O(inf) in worst case.

Permalink

2012-02-02T18:24:25

Of course the first thought is to start at the end ("q") and work your way back to "p", but I suppose that is why you mentioned the whole "p may be connected to q, but q is not necessarily also connected to p".

Permalink

2012-02-02T15:36:51

I assume that we can't use recursion either, as that is just another way to consume memory; so its down to iteration?

Permalink

2012-02-02T02:20:42

Anything to do with digraphs O(n^2)?

Permalink