Filling nxn array in less than O(n^2) time

[crazeinc]

standard 2d array filling

for i=0; i < n; i++
for j=0; j < n; j++
a[ i ][ j ] = i+j


I'm trying to figure out how to do this in less than O(n^2) time, any ideas?

 

[screw3d]

If you are filling it, I don't think you can do it any other way because you still have to go through every single one of them..

 

[kamper]

My instinct says that there is no way, simply because you must, by definition, touch all n^2 elements. But that's the same sort of instinct that says that sorting faster than O(n log n) isn't possible (bucket sort being O(n)) so maybe there is a way.

Besides algorithmic efficiency, if you're looking to shave off any possible time, it's probably possible to avoid recalculating i+j every time and using a ++ per iteration instead. That's pretty nitpicky though. Also, just taking a guess at how a compiler would calculate the location of a[ i ][ j ], you might be able to optimize by treating it as a one dimensional array and using some formula to hit the right location. Is the layout of 2-d arrays a standard? Am I even correct in assuming you're using c here?

Edit: fixing the [ i ]

 

[DaveSimmons]

This should be impossible, since you would have to skip setting elements.

Aside from the semantic tricks and cheap dodges like "use an n-way parallel processing array to do it in O(n)."

If this is for a class and the professor gives a solution, please post it so I can stop rolling my eyes

If this is for real world use and it's (unmanaged) C/C++, you can calculate the memory buffer size (rows*cols*sizeof(-type-)) and do a memset(). but that only works for setting all elements to zero not i+j.

 

[Markbnj]

Only way you could do it would be to unroll the loop (assumes knowing the array dimensions), or do a hack like memset, which another poster suggested (also assumes knowing the array dimensions, not to mention type size).

 

[bersl2]

I don't think you can change the run time to less than O(n^2); however, you might be able to reduce the number of adds by using MMX to add multiple integer quantities, but I wouldn't know if this is worth the effort.

I just noticed that the array values depend solely on the array indexes. Furthermore, the array (when considered a matrix) is symmetric. Depending on how you use it, you may be able to get by with a triagonal matrix and some vectors, or even better. What operations do you perform on this array later on?

 

[oboeguy]

You're kidding, right? You have to write n^2 entries, so O(n^2) writes. Nothing to be done about it.

 

[razor2025]

Impossible.... unless there's some wierd details left out. Keep us posted on solution.