Runtime of Initializing an Array Zero-Filled

Question

If I were to define the following array using the zero-fill initialization syntax on the stack:

int arr[ 10 ] = { 0 };

... is the run time constant or linear?

My assumption is that it's a linear run time -- my assumption is only targeting the fact that calloc must go over every byte to zero-fill it.

If you could also provide a why and not just it's order xxx that would be tremendous!

Answer 1

The runtime is linear in the array size.

To see why, here's a sample implementation of memset, which initializes an array to an arbitrary value. At the assembly-language level, this is no different than what goes on in your code.

void *memset(void *dst, int val, size_t count) {
    unsigned char *start = dst;
    for (size_t i = 0; i < count; i++)
        *start++ = value;
    return dst;
}

Of course, compilers will often use intrinsics to set multiple array elements at a time. Depending on the size of the array and things like alignment and padding, this might make the runtime over array length more like a staircase, with the step size based on the vector length. Over small differences in array size, this would effectively make the runtime constant, but the general pattern is still linear.

Answer 2

This is actually a tip of the ice berg question. What you are really asking is what is the order (Big Oh) of initializing an array. Essentially, the code is looping thru each element of the array and setting them to zero. You could write a for loop to do the same thing.

The Order of magnitude of that loop is O(n), that is, the time spent in the loop increases in proportion to the number of elements being initialized.

If the hardware supported an instruction that says to set all bytes from location X to Y to zero and that instruction worked in M instruction cycles and M never changed regardless of the number of bytes being set to zero, then that would be of order k, or O(k).

In general, O(k) is probably referred to as constant time and O(n) as linear.