The Complexity of Finding Cycles in Periodic Functions
Lists
Only you see this
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...