What is the time complexity of array initializatio

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 theory, both have the same time complexity: O(N), where N is the size of your array.

However, the first method should be better, since it's up to the compiler to choose how to initialize as faster as possible (for instance, it could be done through memset). For optimizations, the compiler is very often better than the programmer.

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

Answer 2

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.