Floyd's Cycle-Finding Algorithm¶

A constant-extra-space method that advances two references at one and two steps along the same successor chain to detect a reachable cycle.

Version: v1 · 2026-10-03 · History
Domain-specific #: 13234
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Algorithms, Data Structures → Computer Science & Software Engineering
Aliases: Tortoise and Hare Algorithm, Floyd's Tortoise and Hare

Core Idea¶

Floyd's cycle-finding algorithm (tortoise and hare) follows one deterministic successor chain from a chosen start with two references. The tortoise takes one step and the hare two each round; a meeting after they begin moving witnesses a reachable cycle. On a partial chain such as a linked list, the hare may instead reach null, proving no reachable loop. A first meeting detects the cycle but need not locate its entry or length.[^{ref-339af01e7547][}ref-534b4a35566b]

Scope of Application¶

In a linked list, successor means a node's next pointer; in a finite iterated function, it means another function evaluation. A total map on finitely many states necessarily reaches a cycle, with tail length \(\mu\) and cycle length \(\lambda\). A list with a terminal null may not. MIT's mathematical-computation lecture and Cornell's linked-list exercise show these unlike settings for the same two-speed method.[^{ref-6adde9bd146f][}ref-a5b2b26efd1a][^ref-339af01e7547]

Clarity¶

Do not conflate the named method with all cycle detection. Brent's method uses a different comparison schedule; a branching-graph cycle search can discover cycles outside a single chosen orbit. Likewise, distinguish detecting repetition from finding its entry or period: resetting one reference to the start and moving both singly can find the entry, and a subsequent circuit counts the period.[^{ref-534b4a35566b][}ref-339af01e7547]

Manages Complexity¶

The method replaces a visited-state table with two moving positions. Once both are on a cycle, the hare gains one position per round modulo the cycle length, so a meeting follows. With constant-cost successor and equality, it uses \(O(\mu+\lambda)\) rounds and \(O(1)\) auxiliary references; the underlying data and the cost of generating a successor are separate. Saving memory can require extra evaluations, especially when entry and period are also wanted.[^{ref-339af01e7547][}ref-a5b2b26efd1a]

Abstract Reasoning¶

First specify a unique successor from the start and whether it can terminate. Then advance one and two steps, compare only after movement, and guard a possibly absent fast successor. A later equality implies a reachable loop; termination implies none on that chain. Do not infer absence of cycles in unvisited graph branches. If entry is required, reset one reference to the start and advance both singly from the first meeting; the second equality is the cycle entry.[^ref-339af01e7547]

Knowledge Transfer¶

A constructed list \(A\to B\to C\to D\to B\) gives a loop whose first fast-slow meeting can be at \(D\), while the entry is \(B\). A constructed finite map \(0\mapsto1\mapsto2\mapsto3\mapsto4\mapsto2\) has \(\mu=2\) and \(\lambda=3\). The same one/two-step and post-start equality roles operate on node identities and mathematical state values, but only the partial list can terminate at null. The proposed parent is live Algorithm, not Cycle or the live frontier-based Search Algorithm identity.[^{ref-339af01e7547][}ref-6adde9bd146f]

[^ref-534b4a35566b]: Peter Gammie, “The Tortoise and Hare Algorithm”, Archive of Formal Proofs (2015), original abstract. [^ref-6adde9bd146f]: John Burkardt, “CYCLE_FLOYD — Cycle Detection by Floyd's Method”, original author-maintained software description. [^ref-339af01e7547]: Cornell CS 2110, “Linked Data,” lecture 13, original course material, exercise 13.11. [^ref-a5b2b26efd1a]: MIT Mathematics 18.783, Lecture 9 slides, original PDF, pp. 13–14.

Relationships to Other Abstractions¶

Current abstraction Floyd's Cycle-Finding Algorithm Domain-specific

Parents (1) — more general patterns this builds on

Floyd's Cycle-Finding Algorithm is a kind of Algorithm Prime

Floyd's two-speed successor procedure is a specific algorithm for deciding whether one reachable orbit repeats.

Hierarchy paths (2) — routes to 2 parentless roots

Floyd's Cycle-Finding Algorithm → Algorithm → Function (Mapping)

Show alternative path (1)

Neighborhood in Abstraction Space¶

Floyd's Cycle-Finding Algorithm sits in a sparse region of the domain-specific corpus (62^nd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Distributed Systems Theorems & Fallacies (19 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08