2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Time complexity depends on the computation model. If your assumptions about the computation model seem to be wrong, then you aren't understand what's happening "under the hood". You might want to ask for clarifications on stackoverflow, since this site is not about the performance of code on actual computers. $\endgroup$ – Yuval Filmus Apr 11 '16 at 7:24
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.