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.