Will this algorithm terminate?

Question

With different values in a collection, will this algorithm (pseudeocode) ever terminate?

while (curElement != average(allElements))
{
    curElement = average(allElements);
    nextElement();
}

Note that I'm assuming that we will re-start from the beginning if we're at the end of the array.

Answer 1

Since this is pseudocode, a simple example with 2 elements will reveal that there are cases where the program won't terminate:

x = 0, y = 1;

          x     y
Step 1:   0.5   1
Step 2:   0.5   0.75
Step 3:   0.635 0.75
//and so one

With some math involved, lim(x-y) = lim( 1 / 2^n )

So the numbers converge, but they're never equal.

However, if you'd actually implement this on a computer, they will turn out equal because of hardware limitations - not all numbers can be expressed in a limited number of bits.

Answer 2

It depends.

If your elements hold discrete values, then most likely they will fall into the same value after a few runs.

If your elements hold limited precision values (such as floats or doubles), then it will take longer, but finite time.

If your elements hold arbitrary precision values, then your algorithm may never finish. (If you count up every piece of an integral and add it to a figure you have on a piece of paper, you need infinite time, an infinitely large piece of paper, and infinite patience with this analogy.)

There is little difference between your code and the following:

var i = 1;
while (i != 0) 
    i = i / 2;

Will it ever terminate? That really depends on the implementation.