Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Regarding Floyd's cycle-finding algorithm

  1. Jun 15, 2008 #1
    Well I understand what is happening - the tortoise moving 1 step, and the hare moving 2 steps and finally coinciding at a point. But I want a mathematical proof of this - ie; when you have 2 counters moving in a cycle, one going 1 step, the other 2 steps, then they finally meet at a point.
  2. jcsd
  3. Jun 15, 2008 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Suppose that they start M places apart (suitably oriented) on a cycle of size N. How many places apart are they after k steps?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook