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.

What does nextElement() do and is the allElements() collection constant? — Roy Dictus
– Roy Dictus, Commented Feb 10, 2012 at 9:48
It depends on your values in that collection. average(allElements) will return fractional values or absolute? — Shashank Kadne
– Shashank Kadne, Commented Feb 10, 2012 at 9:49
@RoyDictus: It's supposed to be pseudocode. Just imagine that nextElement() moves the pointer curElement to the next element of the collection, or to the beginning if we're at the end. — Franz
– Franz, Commented Feb 10, 2012 at 9:51
@RoyDictus: Oh, and allElements will be changed when curElement is set. — Franz
– Franz, Commented Feb 10, 2012 at 9:51

Luchian Grigore · Accepted Answer · 2012-02-10 09:59:28Z

5

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.

answered Feb 10, 2012 at 9:59

Luchian Grigore

260k68 gold badges465 silver badges634 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

user684934 Over a year ago

There exist arbitrary precision real-number implementations, which would allow for a real-life implementation to run forever.

Luchian Grigore Over a year ago

@bdares I doubt that. They still store the number in memory, and as large as it gets, it's not infinite.

amit Over a year ago

@LuchianGrigore: You can store the number in disk/remote cluster and expand it on the fly. Theoretically, it can be done.

user684934 Over a year ago

Hmmm... good point. @amit any real-life storage is finite, so his argument still holds.

amit Over a year ago

@bdares: (1) You can expand the cluster on the fly, so it is infinite. (2) You could say that the universe will collapse at some point in time, and there are finite number of atoms in the universe, so every implementation of any algorithm is O(1) space & time. But I don't think that's what the discussion is about.

|

score 2 · Accepted Answer · 2012-02-10 09:56:18Z

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.

Collectives™ on Stack Overflow

Will this algorithm terminate?

2 Answers 2

7 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

Comments

Related