Lower bounds for the cycle detection problem
- 1 January 1981
- proceedings article
- Published by Association for Computing Machinery (ACM)
- Vol. 26 (3) , 96-105
- https://doi.org/10.1145/800076.802462
Abstract
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.This publication has 0 references indexed in Scilit: