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(logn)$	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

Space Complexity graph

Pareto Decades graph

References/Citation

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