Costs of updating arrays to contain only zeroes

Question

To initialize an array of length $n$ has complexity $O(n)$, as far as I understand. If I set every element to zero (with one code line), does that have time complexity $O(n)$ also?

And in that case, setting an $n$-array to zero inside a loop with $n$ iterations should be $O(n^2)$, right? I am asking because I have written some code that does this, but the runtime only increases linearly when I increase $n$, not quadratically as I would have expected, so I don't quite understand. Is it perhaps to do with the compiler?

Answer 1

To initialize an array of length n has complexity O(n), as far as I understand. If I set every element to zero (with one code line), does that have time complexity O(n) also?

The answers to both questions depend on the machine model. In common ones, like e.g. the RAM model, writing every memory cell take a constant amount of time $c$. Hence, intializing an array of length $n$ takes time $cn + d \in \Theta(n)$, with $d$ being some constant overhead.

Now, doing

arr = new array[n]
for i = 0 to n-1
  arr[i] = some_value
end

incurs both the cost for initializing arr plus the cost for the for-loop, which is not too hard to analyse. It has, in fact, linear runtime cost (with common RAM-model assumptions).

setting an n-array to zero inside a loop with n iterations should be O(n²), right?

I don't understand your algorithm perfectly, but if you mean above code with some_value = 0 then no. The total running-time cost is linear since costs add up.

If you mean something like

arr = new array[n]
for i = 0 to n-1 
  setAllToZero(arr)
end

then it depends on how set_all_to_zero is implemented. If it contains an explicit loop, then we'd expect quadratic runtime cost. If there are machine-level instructions to set a whole stretch of memory to zero, it may be faster.

The same holds for array initialization, by the way: if the machine (model) does not guarantee any specific value after array intialization, or has some nifty way to ensure zeroes everywhere without extra cost, array initialization may only take constant time.