Cycle Detection (Cycle Detection)
Jump to navigation
Jump to search
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
Error creating thumbnail: Unable to save thumbnail to destination
Space Complexity Graph
Error creating thumbnail: Unable to save thumbnail to destination
Time-Space Tradeoff
Error creating thumbnail: Unable to save thumbnail to destination