View source for Floyd's Cycle Detection

'''Floyd's cycle detection algorithm''', also known as the "tortoise and hare" algorithm, is a pointer algorithm that detects cycles in linked lists and iterated sequences using only constant space. Invented by Robert W. Floyd in the 1960s, the algorithm advances two pointers through the sequence at different speeds — one moving one step at a time (the tortoise), the other moving two steps at a time (the hare). If the sequence contains a cycle, the hare will eventually lap the tortoise; if not, the hare reaches the end. The algorithm's elegance lies in its O(1) space complexity, a property that makes it indispensable in memory-constrained settings and the theoretical foundation for cycle-finding in [[Pollard's Rho Algorithm|Pollard's rho algorithm]] and other factorization methods.

''Floyd's algorithm is a reminder that the most powerful ideas in computer science often arrive with minimal resource requirements. The tortoise and hare do not need a map of the terrain they traverse; they need only the discipline of different speeds. This is not merely an algorithmic trick. It is a paradigm: when you cannot store the path, encode information in the relative motion of multiple traversals.''

[[Category:Computer Science]]
[[Category:Algorithms]]