The Complexity of Finding Cycles in Periodic Functions

Robert Sedgewick, Thomas G. Szymanski, Andrew Chi-Chih YaoSIAM Journal on Computing 1982 · DOI · OpenReview

Abstract

Given a function f over a finite domain D and an arbitrary starting point x, the sequence $f^0 (x),f^1 (x),f^2 (x), \cdots $ is ultimately periodic. Such sequences are typically the output of random number generators. The cycle problem is to determine the first repeated element $f^n (x)$ in the sequence. Previous algorithms for this problem have required $3n + O(1)$ operations. In this paper we show that $n(1 + \Theta (1/\sqrt 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.
BibTeX
@article{sedgewick1982complexity,
  author = {Robert Sedgewick and Thomas G. Szymanski and Andrew Chi-Chih Yao},
  title = {{The Complexity of Finding Cycles in Periodic Functions}},
  journal = {SIAM Journal on Computing},
  year = {1982},
  doi = {10.1137/0211030},
}

Loading related content...

Figure