Gosper's algorithm ( Cycle Detection)
Revision as of 11:15, 15 February 2023 by Admin (talk | contribs) (Created page with "== 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")
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