What is the time complexity of array initialization?

Question

Consider two cases of array initialization in C or C ++:

Case 1:

int array[10000] = {0}; // All values = 0 

Case 2:

 int array[10000]; for (int i = 0; i < 10000; i++) { array[i] = 0; } 

Do they both take the same time? What is the complexity of case 1? and which one is better?

Answer 1

In the case when the array has a static duration (global variable), I would say that the first one is preferable, since it does not require any code - it is initialized by the runtime.

If the variable has an automatic duration (local variable), which one is better, if it is better than the other, it depends on the compiler. Most likely, both will be very similar.

The difficulty for the variable duration of automatic storage is O (n) for all cases. The first case is O (1) for a variable static storage duration.

Of course, if you want to fill the array with a value of 5, the second option is much better, because it does not require writing 10000 5 to the source file.

You may also find that using memset(array, 0, sizeof(array)); better than both again, depending on the compiler. This is still O (n), but the actual time it takes to fill the array may be shorter because memset can be better optimized than what the compiler generates for your loop case [and what it does for initialized variables]. memset will not work to populate an array with 5 .

You can also use std::fill(array, &array[10000], 5); to set the value to 5 in the whole array, and the compiler must do a decent job of optimizing it.

Lastly, I must point out that such things REALLY matter if they do in code that runs a lot. This is a long time, as filling in 40 Kbytes of data took a lot of time to really worry about yourself. Like 20+ years.

Answer 2

In theory, both have the same complexity: O(N) , where N is the size of your array.

However, the first method should be better, since it is up to the compiler to choose how to initialize as quickly as possible (for example, this can be done using memset ). For optimization, the compiler is often better than the programmer.

BTW, if your array has a static storage duration (if you declare it as a global variable, for example), it will be automatically initialized to 0.