1
$\begingroup$

Givens. I understand Floyd's algorithm can determine the length $\lambda$ of the loop and the length $m$ of the tail. The hare will not necessarily catch the tortoise on the first cycle, but it is guaranteed to catch it after a number $k$ of cycles, where $k$ is a natural number.

Question. Given I know these facts, how can I deduce the worst case complexity of the algorithm?

An answer that seems fallacious. For the tortoise and the hare to meet, they both need to be in the cycle. This will occur certainly after $\mu + \lambda$ iterations. Once the tortoise is in the cycle, the distance between the tortoise and the hare diminishes by one at each iteration. Yuval Filmus' answer shows that they meet in the cycle in an index that's a multiple of $\lambda$. Therefore, after they're both in the cycle, after $\lambda$ iterations (in the worst case) they must have reduced their distance to zero --- because the largest distance between them in the cycle is $\lambda$. But how do I know the hare didn't jump the tortoise? This argument doesn't seem very good.

$\endgroup$
2
$\begingroup$

(Adapted from a StackOverflow answer.)

The tortoise arrives at the loop on iteration $\mu$. Since the hare moves faster, it is already in the loop. From the hare's perspective, the tortoise is now some distance ahead of it, and that distance is certainly less than $\lambda$.

Since the hare gets one step closer to the tortoise on each iteration, it will catch up in less than $\lambda$ more iterations, for a worst-case total of $\mu+\lambda-1$.

It is impossible for the hare to pass the tortoise without them both occupying the same spot. Suppose the hare is one step behind. Then, on the next iteration they will be on the same spot. If, on the other hand, the hare is more than one step behind, it will still be behind after the next iteration because it only gets one step closer.

Yuval's proof is much more precise and mathematical, and is certainly correct. But this simple explanation seems to have a certain intuitive value.

$\endgroup$
  • $\begingroup$ Yes, I see you argument... You've added the missing part of my fallacious argument above. That's a very nice addition because it is surely intuitive. But this argument begs the reader to jump to conclusion. It convinces me --- but convincing me is easy. :-) I'm going to revise Yuval's proof because I haven't seen yet why they meet on the first cycle run. $\endgroup$ – R. Chopin Feb 21 at 1:47
  • $\begingroup$ Your answer, which is excellent, should be given to this question because the OP asked for an intuitive proof and Yuval gave a rigorous, non-intuitive proof. But, over here, I'm really more interested in Yuval's brilliant argument, so I'll accept his answer as soon as I really see it --- just so I don't confirm something I, out of my inability, couldn't confirm. (But thanks so much for this very great insight into the problem.) $\endgroup$ – R. Chopin Feb 21 at 2:40
  • 1
    $\begingroup$ @R.Chopin: for the question "how do I know the hare didn't jump the tortoise?", there's a simple proof by induction lurking in my answer. Induction is certainly rigorous and can be intuitive if your intuitions are that way inclined. Honestly, I think the two questions are dupes but I'm not going to push it. $\endgroup$ – rici Feb 21 at 2:56
  • $\begingroup$ That's a very good point and I can write that proof myself. $\endgroup$ – R. Chopin Feb 21 at 12:03
2
$\begingroup$

In this answer, I show that $x_i = x_{2i}$ iff $i \geq \mu$ and $i$ is a multiple of $\lambda$. In particular, this will happen for some index $i$ in the range $\{\mu,\ldots,\mu+\lambda-1\}$. This shows that the algorithm runs in time $O(\mu + \lambda)$.

$\endgroup$
  • $\begingroup$ I can't see how it follows that if $i$ is a multiple of $\lambda$ then the algorithm terminates with $O(\mu + \lambda)$ comparisons. $O(\mu + \lambda)$ comparisons means there is a constant $c$ such that the exact number of comparisons performed by the algorithm is less than or equal to $c (\mu + \lambda)$. Maybe I see it. Let k be the number of comparisons computed by the algorithm and define $c = k$. Is what you have in mind? $\endgroup$ – R. Chopin Jan 15 at 12:37
  • $\begingroup$ You can take $c = 1$. $\endgroup$ – Yuval Filmus Jan 15 at 14:29
  • $\begingroup$ Why $c = 1$? How do I know that $\mu + \lambda$ is always greater than the number of comparisons performed by the algorithm --- that could cycle many times before finding a collision? $\endgroup$ – R. Chopin Jan 15 at 15:14
  • $\begingroup$ All the information you need to understand that is in my answer. $\endgroup$ – Yuval Filmus Jan 15 at 15:27
  • 1
    $\begingroup$ My answer shows that they meet in the first index after $\mu$ which is a multiple of $\lambda$. This index is smaller than $\mu + \lambda$. $\endgroup$ – Yuval Filmus Feb 18 at 2:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.