I understand in Floyd’s cycle, you are finding a cycle in a linked list by moving two counters- one by a factor of 2, other by a factor of 1. In Brent’s you are basically doing the same but the one factor moves by multiplying 2 instead by merely adding 2. Is there any math explanation behind why Brent’s is faster than Floyd’s?


merged by D.W. Sep 7 '16 at 18:32

This question was merged with Why is Brent's Cycle Detection method faster at finding a Linked List cycle than Floyd's Cycle Detection method? because it is an exact duplicate of that question.