Cycle Detection (Cycle Detection)

Description

Cycle detection or cycle finding is the algorithmic problem of finding a cycle in a sequence of iterated function values.

Parameters

$t_f$: time to perform one evaluation of $f$

$\mu$: the starting index of the cycle

$\lambda$: the period of the cycle

$M$: number of values stored

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Sedgewick; Szymanski; and Yao	1982	$(\mu + \lambda)({1}+\Theta({1}/sqrt(M)))$	M	Exact	Deterministic	Time & Space
Nivasch	2004	$O(\mu + \lambda)$	$O(\log\mu)$	Exact	Deterministic	Time & Space
Floyd's tortoise and hare algorithm	1967	$O((\lambda + \mu)$ t_f)	$O({1})$	Exact	Deterministic	Time
Brent's algorithm	1973	$O((\lambda + \mu)$ t_f)	$O({1})$	Exact	Deterministic	Time
Gosper's algorithm	1978	$O((\lambda + \mu)$ log(\lambda + \mu) t_f)	\Theta(log(\mu + \lambda))	Exact	Deterministic	Time & Space

Time Complexity Graph

References/Citation

https://www.sciencedirect.com/science/article/pii/0304397585900441?via%3Dihub