Cycle detection using a stack
We present an algorithm for detecting periodicity in sequences produced by repeated application of a given function. Our algorithm uses logarithmic memory with high probability, runs in linear time, and is guaranteed to stop within the second loop through the cycle. We also present a partitioning technique that offers a time/memory tradeoff. Our algorithm is especially well suited for sequences where the cycle length is typically small compared to the length of the acyclic prefix. (C) 2004 Elsevier B.V. All rights reserved.
cycle detection stack algorithms time/memory tradeoffs analysis of algorithms random function