Re: Filling 2d array in less than O(n^2)?

pjhyett@xxxxxxxxx wrote: 
That's what I'm thinking about

If you look at the output for 4x4 it looks like

0 1 2 3
1 2 3 4
2 3 4 5
3 4 5 6

and I'm thinking there's a way to take advantage of the fact that some
numbers are repeated.


But given that you have n^2 elements to fill and there must be at least
one elementary operation for each element (to write to it),
that means n^2 is also a lower bound.

Or am i missing something here?
.