Gosper's algorithm ( Cycle Detection)
Jump to navigation
Jump to search
Time Complexity
$O((\lambda + \mu)$ log(\lambda + \mu) t_f)
Space Complexity
\Theta(log(\mu + \lambda))
(https://en.wikipedia.org/wiki/Cycle_detection#Gosper's_algorithm)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Year
1978
Reference
https://www.inwap.com/pdp10/hbaker/hakmem/flows.html#item132