# Efficient Array Normalization

I want to normalize elements in an array. The solution I found is to take the sum of the elements and divide each element with this total. Can you find more efficient way of doing this?

The runtime I achieve is 2N. Any better idea?

normalize(array)
{
sum = 0;

for i = 0 to array.size() do
sum += array[i];
end

for i = 0 to array.size() do
array[i] /= sum;
end
}


Given that at least N "operations" are needed since each array element is affected, you can't get the number of operations down by much. It's not clear what your complexity measure exactly is – why is sum += array[i] a single operation? What about the loop? The actual CPU needs to increment i and compare it to array.size(), there are jumps involved and so on. The operation sum += array[i] is probably more than one instruction. Not to mention things you actually forgot to count, like sum = 0.