1982/05/01 by Robert Sedgewick, Thomas G. Szymanski, Andrew Chi-Chih Yao · 3 citations
Computer Science · Mathematics · #Algorithms and Data Compression #semigroups and automata theory #Advanced Combinatorial Mathematics #Sequence (biology) #Function (biology) #Mathematics #Combinatorics #Element (criminal law) #Domain (mathematical analysis) #Discrete mathematics #Random sequence #Algorithm #Point (geometry) #Mathematical analysis
paper · doi:10.1137/0211030
openalex publication_date 1982/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
Given a function f over a finite domain D and an arbitrary starting point x, the sequence f0 (x),f1 (x),f2 (x), ⋯ is ultimately periodic. Such sequences are typically the output of random number generators. The cycle problem is to determine the first repeated element fn (x) in the sequence. Previous algorithms for this problem have required 3n + O(1) operations. In this paper we show that n(1 + Θ (1/√ M )) steps are both necessary and sufficient, if M memory cells are available to store values of the function. We explicitly consider the performance of the algorithm as a function of the amount of memory available and the relative cost of evaluating f and comparing sequence elements for equality.