generating points on a grid - efficiently

[Stephen Horne]

On Mon, 08 Mar 2004 20:03:43 -0800, Josiah Carlson
<jcarlson at nospam.uci.edu> wrote:

>> Firstly,  the code runs in exponential time. Is there any way to
>> rewrite it to make it more efficient? It seems that this could be
>> formulated as a recursive problem but I can't seem to get at it.
>
>The code does not run in exponential time.  It runs in linear time to 
>the number of grid points that exist.  Depending on your input, this can 
>vary.

It is exponential in the number of dimensions, making various
assumptions (mainly that all ordinalities are roughly equal). It is
polynomial in the ordinality of dimensions, again with assumptions
(constant number of dimensions, all ordinalities roughly equal). It is
linear in the number of grid points. It is constant time, for a
specific set of inputs.

When you write O(n), formally you have to define what n means. But I
don't think Rajarshi needed to be so formal. His intention should have
been clear, though - he didn't intend O(n^k), but rather O(k^n) where
n is the number of dimensions - making performance exponential.

The real problem is that the number of output grid points is obviously
exponential in the number of dimensions (or polynomial in the
ordinalities, etc) so it's impossible to improve on this performance
characteristic while still generating all the grid points - only the
constant scalings can be improved.


-- 
Steve Horne

steve at ninereeds dot fsnet dot co dot uk