Intuitive proof for Floyd's cycle detection algorithm

Question

I am trying to understand Floyd's cycle detection algorithm. I can see why the algorithm works.

When the Hare moves twice as fast as Tortoise, if there is cycle, they will meet definitely at some point in the cycle.

Is there any proof that proves the above point? I mean, without assuming that Hare and Tortoise meet at some point when Hare moves twice the speed of Tortoise and then proving.

In the wiki, I can understand the following paragraph.

The key insight in the algorithm is that, for any integers $i ≥ μ$ and $k ≥ 0, x_i = x_{i + kλ},ドル where λ is the length of the loop to be found and μ is the index of the first element of the cycle

But it is followed by the following point which I could not understand.

in particular, $i = kλ ≥ μ,ドル if and only if $x_i = x_{2i}$. Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period ν of a repetition that is a multiple of λ

How does the author come to conclusion that $i = kλ ≥ μ,ドル if and only if $x_i = x_{2i}$

Can somebody please help me in understanding this?

• klaus: This other question might help cs.stackexchange.com/questions/10360/…
• Arun Rahul: Thanks for the link. But I want the proof for the first part of the algorithm i.e., I want to prove (without assuming anything) that fast pointer meets slow pointer at some position $i$

Answer 1

By definition, $x_0,\ldots,x_{\mu+\lambda-1}$ are all distinct, and for $i \geq \mu,ドル we have $x_{i+\lambda} = x_i$. Now let us prove the claim:

Let $i \geq 1$. Then $x_i = x_{2i}$ if and only if $i \geq \mu$ and $i = k\lambda$ for some $k \geq 1$.

$\Longleftarrow$ Suppose that $i \geq \mu$ and $i = k\lambda$. Since $i \geq \mu,ドル we have $x_{i+t\lambda} = x_i$ for all $t \geq 0$. In particular, choosing $t := k,ドル we get $x_{2i} = x_{i+k\lambda} = x_i$.

$\Longrightarrow$ Suppose that $x_i = x_{2i}$. If $i < \mu$ then $x_j = x_i$ if and only if $j = i$. Since 2ドルi \neq i$ (as $i \neq 0$), this contradicts the assumption $x_i = x_{2i},ドル showing that $i \geq \mu$.

Since $i \geq \mu,ドル $x_i = x_{\mu + [(i-\mu) \bmod \lambda]}$. Similarly, $x_{2i} = x_{\mu + [(2i-\mu) \bmod \lambda]}$. Since $x_\mu,\ldots,x_{\mu+\lambda-1}$ are all distinct, it follows that $i-\mu \bmod \lambda = 2i-\mu \bmod \lambda,ドル and so $i$ is a multiple of $\lambda$.

• R. Chopin: I haven't been able to understand why $i - \mu \mod \lambda = 2i - \mu \mod \lambda$ implies $i$ is a multiple of $\lambda$. Can you clarify what facts leads me into that conclusion? Thank you.
• Yuval Filmus: Just subtract the two to obtain $i \equiv 0 \pmod \lambda$.
• R. Chopin: (Wow, I couldn't see that.) Thank you so much. (Very well written proof!)

Answer 2

The idea is to find the multiples of λ (the cycle length). if index i=kλ is the first node of the cycle or inside the cycle for some k≥0, Then any number of cycles after that will just get you to that same point. i.e a faster pointer will make mkλ loops. m being the ration of hare to tortoise speed.

m=2 is optimal as it makes least number of rounds. Tortoise will end up at index i=kλ and hare ends up at 2kλ, the same point.

Here is a good post https://ivanyu.me/blog/2013/11/24/finding-a-cycle-in-a-linked-list/