Question

Proof

Prove that the Tortoise and the Hare algorithm will terminate if there is a cycle

Answer 1

If there is a cycle when applying the Tortoise and Hare algorithm, the Hare will enter the cycle before Tortoise does, and once entered in a cycle, the Hare will remain in the cycle until the algorithm terminates, as there is no way to get out of the cycle.

Now, after Tortoise also enters the cycle, the distance between Tortoise and Hare decreases by one (either in a clockwise or anticlockwise direction) every time Hare and Tortoise pointers are moved.

Thus, in a finite amount of time an instance will come when the distance between them is zero (i.e. they both point to the same node) and thus algorithm will terminate at this point.