3 ms·
The tortoise and the hare solution is quite elegant though. This approach is more correctly known as Floyd's cycle-finding algorithm, and while it is suboptima
by cperciva 19y ago
The tortoise and the hare solution is quite elegant though.
This approach is more correctly known as Floyd's cycle-finding algorithm, and while it is suboptimal, it comes within a constant factor of the optimum for logspace algorithms.
- smanek 19y agoJust for my own edification, what is the optimal solution? I haven't yet seen a proof on the lower bound of cycle detection, so I don't know if other quicker solutions (like Brent's algorithm) are optimal or are just the best we've found. And I don't think there is anything incorrect with referring to Floyd's cycle-finding algorithm as the tortoise and the hare algorithm. Most literature I've seen mentions the alias too.