Lower bounds for the cycle detection problem

摘要

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.