CODEWITHSUNDEEP
algorithmlinked-list
1step1leap
1step1leap

Reputation: 605

Floyd's cycle detection algorithm: Why does the tortoise only do at most one lap?

Why does the Floyd's cycle detection algorithm assume that the tortoise will do at most a single lap around the cycle before it meets with the hare? Why can't it do multiple laps? Both the intuitive and formal explanation would be greatly appreciated.

Upvotes: 1

Views: 197

Answers (1)

shapiro yaacov
shapiro yaacov

Reputation: 2346

I think I can provide an intuitive explanation.

We can have two cases: either there is a cycle, or not.

If there is no cycle:
The hare will get to the end of the list before the tortoise does and so we're done.

If there is a cycle:
It must be of length n and we remember that the "speed" of the hare is twice that of the tortoise's.
Once the tortoise enters the loop, the hare is somewhere in the cycle (might have gone around it a few times already). In any case, it is x nodes behind the tortoise (Remember that x <= n-1 because if they were on the same node we'd end here).
Since the "speed" of the hare is twice that of the tortoise, it will "catch up" with it within x "steps".
QED.

Upvotes: 1

Related Questions