Efficient Array Normalization

Question

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
}

Answer 1

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.

That said, I can't see how to improve on your algorithm, and I don't think it's possible, though as mentioned above, the notion of complexity is very shaky here, so perhaps there is a "trick" which will work under your complexity measure, whatever it is.