generating points on a grid - efficiently

[Josiah Carlson]

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

You do make a good point, and additionally proper algorithm analysis 
takes into account the data representation size of the input and output.

If my input is a list of j sublists, certainly my input size is the sum 
of the length of each sublist (times the size of each element, which I 
will assume constant), which I will call m.  However, my output, no 
matter how many lists there are, is of size o(j * m^j) (yes, that was 
little o).  Now, looking at the actual problem, we have output of size 
exactly: j*len(sublist1)*len(sublist2)*len(sublist3)...

In the extreme conditions:
m*1^m <= size(output) <= (m/3)*3^(m/3)
m     <= size(output) <= m*3*(m/3 -1)

Indeed, the output size (and time) /is/ worst-case exponential in the 
size of the input.  We get that '3' either through numerical testing, or 
through calculus, which would give us 'e' as producing the largest size 
output.  Testing both 2 and 3 show us that 3 is larger.

I should have done the math in the initial post, thank you for pointing 
out my initial mistake, and allowing me to prove it mathematically.

  - Josiah