Why does Floyd’s Cycle detection algorithm work?

Key takeaways:

• Cycle detection involves identifying repeated values in iterative sequences that form a loop.
• Floyd’s Algorithm, also known as the Tortoise and Hare method, detects cycles using two pointers moving at different speeds.
• The intersection point of the cycle is where the faster-moving hare meets the slower-moving tortoise.
• The starting point of the cycle is determined by resetting one pointer to the beginning and moving both pointers at the same speed.
• The algorithm is mathematically proven by showing that the cycle length equals the sum of distances traveled by the pointers.
• Floyd’s Algorithm is efficient, with a time complexity of $𝑂(𝑛)$ and a space complexity of $O(1)$.
• It reliably detects cycles, even if the starting distance exceeds the cycle length, due to the periodic nature of traversal.
• The algorithm is widely applied in linked lists, iterative sequences, and preventing infinite loops.

In computer science, cycle detection, or cycle finding, is a fundamental problem that revolves around finding cycles in a sequence of iterated function values. When working with a function $f$ that maps a finite set of values $S$ to itself and given an initial value $x_0$ in $S$, the iterated sequence of function values eventually repeats itself, forming a cycle.

The sequence of iterated function values can be represented as:

$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space x_0, \space x_1=f(x_0),\space x_2=f(x_1) \space. \space.\space.\space, \space x_j =f(x_{j-1})\space,\space.\space. \space.$

The sequence above will eventually lead to the same value appearing twice. In other words, there will exist distinct indices $i$ and $j$ such that $x_i = x_j$. Once this cycle is detected, the sequence will continue to repeat the same values periodically, starting from $x_i$ and ending at $x_{j-1}$. The goal of cycle detection is to identify these indices $i$ and $j$, where $x_i$ represents the starting point and $x_{j-1}$ represents the intersection point of the cycle, based on the function $f$ and the initial value $x_0$.

Let’s look at the following illustration to better understand cycle detection.

How Floyd’s cycle detection algorithm works

Floyd’s cycle algorithm is one of the algorithms used to detect whether a linked list or array representation of the data has a cycle in it and what is the starting point of that cycle. It is also known as the tortoise and hare algorithm.

Recap

In this algorithm, the two pointers, tortoise and hare, traverses the data structure. The tortoise pointer moves one step at a time, while the hare pointer moves twice as fast as the tortoise pointer. Due to moving twice as fast as the tortoise pointer, the hare pointer catches up to the tortoise pointer at a certain point if a cycle exists. This point is known as the intersection point of the cycle.

Note: The point from where we enter the cycle is known as the starting point of the cycle. It can be found by traversing the array one more time. Now, move the hare pointer from the intersection point and the tortoise pointer from the start of the data structure but at the same speed.

Let’s look at a visual representation of detecting a cycle, finding the intersection point, and the starting point of the cycle in an array.

Why Floyd’s cycle detection algorithm is always effective

Now let’s see why Floyd’s cycle detection algorithm is always able to detect the cycle and find its starting point.

Let’s look at the example again, having a scenario where a cycle is present in the array.

In the diagram above:

• $7$ is the intersection point where the hare and tortoise pointers meet.

• $8$ is the starting point of the cycle.

The hare pointer is traversing two times faster than the tortoise pointer. This can be represented by the following equation:

$d _{\text{hare}} = 2d_{\text tortoise}$ ——— $(1)$

Here, $d$ represents the number of elements traversed.

Let’s look at the following diagram to see the steps taken by the tortoise and hare pointers from the start of the array to the intersection point:

In the diagram above:

• Green represents the starting point of the cycle.

• Blue represents the intersection point.

• Yellow represents the start of the array.

• $F$ represents the steps taken from the start of the array to the starting point of the cycle.

• $a$ represents the steps taken from the starting point to the intersection point.

• $C$ represents the cycle length, in terms of the number of steps taken to go once around the cycle.

With this setup in mind, let’s see the distance traveled by the tortoise and hare pointers.

The tortoise pointer travels $F$ steps from the start of the array to the starting point of the cycle and then takes $a$ steps from the starting point to the intersection point of the cycle, that is, the point where both pointers meet. So, we can express the distance traveled by the tortoise pointer in the form of this equation:

$d _{\text tortoise} = F + a\space$———$\space(2)$

In the time it takes the tortoise pointer to travel $F+a$ steps, the hare pointer, since it’s traveling twice as fast as the tortoise pointer, will have also traveled around the cycle at least once. So, we can say the hare pointer, first, travels $F$ steps from the start of the array to the starting point of the cycle, then travels at least a cycle, and at the end travels $a$ steps from the starting point to the intersection point of the cycle. Now, we can express the distance traveled by the hare pointer as the following equation:

$d _{\text hare} = F + C + a\space$———$\space(3)$

Recall eq. $(1):$

$d _{\text hare} = 2d_{\text tortoise}$ ——— $(1)$

If we substitute the equivalent expression of $d_{\text tortoise}$ given in eq. $(2)$ and the equivalent expression of $d_{\text hare}$ given in eq. $(3)$ into eq. $(1)$, we get:

$F+C+a = 2(F+a)$

Let’s simplify this equation:

$F+C+a = 2F+2a$

$C = F+a$

Therefore, the distance from the start of the array to the intersection point, $F+a$, equals $C$.

We can also re-arrange this equality as follows:

$F=C-a$

Let’s recap our diagram again.

As we can see, $C-a$ is, in fact, the distance from the intersection point back to the starting point of the cycle. This illustrates why, when we move hare pointer forward, starting at the intersection point, and the tortoise pointer from the start of the array, the point where they meet again is the starting point of the cycle.

That is why Floyd’s Cycle detection is always able to locate the starting point of the cycle.

Time to ponder: What if $F$ is longer than the length of the cycle?