1981/01/01 by Faith E. Fich · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Advanced Combinatorial Mathematics #Machine Learning and Algorithms #Sequence (biology) #Function (biology) #Repetition (rhetorical device) #Upper and lower bounds #Domain (mathematical analysis) #Algorithm #Computer science #Element (criminal law) #Combinatorics #Discrete mathematics #Mathematics #Mathematical analysis
paper · doi:10.1145/800076.802462
openalex publication_date 1981/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Given a function f over a domain and an element x in the domain, the cycle detection problem is to find a repetition in the sequence of values x, f(x), f(f(x)), f3(x),. . . , if one exists. This paper investigates lower bounds on the number of function evaluations needed when there is a bound on the amount of memory available. For certain restricted classes of algorithms which use two memory locations optimality is achieved. A summary of the major results appears in the final section.