What is the time complexity of array initialization?

Question

Consider following 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 same time ? what is the complexity of Case 1? and, Which one is better?

Answer 1

In the case of the array being of static duration (global variable), I'd say the first one is much preferrable, since it doesn't require any code - it is initialized by the runtime-environment.

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

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

Of course, if you wanted to fill array with the value 5, the second option is much better because it doesn't require writing 10000 5 in the source file.

You may also find that using memset(array, 0, sizeof(array)); is 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 may be better optimized than what the compiler generates for your loop case [and what it does for initialized variables]. memset won't work for filling the array with 5 either.

You could also use std::fill(array, &array[10000], 5); to set the value 5 in all the array, and the compiler will should a decent job of optimizing that.

Finally, I should point out that these sort of things only REALLY matter if they are doing in code that gets executed a lot. It's a long time since filling 40KB of data took long enough to really worry about on its own. Like 20+ years.