= Floyd's cycle-finding algorithm
{c}
= Floyd cycle-finding algorithm
{c}
{synonym}
= Floyd’s cycle detection
{c}
{synonym}
For a deterministic iteration $x_{n+1}=f(x_n)$ on a <finite set>, move one pointer by one step and another by two steps. They eventually meet inside the repeated cycle. Restarting one pointer at the initial state and advancing both by one step locates the cycle entrance; a further traversal measures its length. The method uses constant extra <space complexity> and time proportional to the preperiod plus cycle length.
Back to article page
