1
$\begingroup$

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
}
$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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