initializing an n elements array using O(1) performence ?

Question

someone has an idea how can I do that ?

thanks

Answer 1

This smells like a homework problem but I'll throw you a bone...

http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time/

Answer 2

If you mean "initialize a dense array of N items in a time independent of N", then it is physically impossible. A dense array has a storage space that grows linearly with the number of items, and it will take a linear amount of time to initialize this space.

You can have constant-time initialization using a sparse array. That is essentially an associative array (or hashmap, or dictionary, or table, depending on the language) which initializes items when they are first accessed.

Answer 3

If you need to do something to each element of a set of n elements, you cannot do it with better than O(n) performance.

Answer 4

I think its just a simple syntax question. In C++ you can do this:

int foo[1000] = {0};

All values in array are now 0

While it looks like its done in constant time, it still O(n)

Answer 5

No. It's physically impossible. However, you can use vector instructions to make it some O(n * 1/k) time, where k is the width of a vector setter instruction. That's still O(n), but the constant is shrunk.

Answer 6

Actually, it is possible, but only with hardware help. On software, you will have to do a number of steps proportional to n, thus it is O(n); on hardware, however, you can wire things so that all elements of the array are set in parallel.

This is in fact a time/space tradeoff; while before one needed O(n) time, now one needs O(n) circuit elements but can do the operation in O(1) time.

And it is actually a common thing to do. A lot of hardware has a reset input which, when asserted, sets the whole hardware to a known state. This can involve for instance zeroing the whole memory.