Is the turtle and rabbit algorithm always O (N)?

Question

I will talk about this with the fact that I am not fully aware of Big O Notation, so maybe my thinking about it does not work.

I accidentally searched for SO when I came across the issue of detecting infinite loops in Linked Lists. It pointed to an algorithm here known as Turtle and Rabbit.

class Node { Node next; } boolean isInInfiniteLoop(Node node) { if (node == null) { return false; } Node turtle = node; // slower moving node Node rabbit = node.next; // faster moving node while (rabbit != null) { if (rabbit.equals(turtle)) { // the faster moving node has caught up with the slower moving node return true; } else if (rabbit.next == null) { // reached the end of list return false; } else { turtle = turtle.next; rabbit = rabbit.next.next; } } // rabbit reached the end return false; } 

In the article, he mentions that it is O (N). From what I understand, O (N) means that the speed of the algorithm grows linearly with respect to the number of elements in the list.

However, if I don’t look at something wrong, the rabbit variable always skips 1 node (so it’s “faster”), which means that it has the potential to skip the node turtle, thereby having the loop potential around an infinite loop of 1 or more times before it becomes the same node as the turtle, which will mean that the worst case scenario is not O (N).

Am I missing something? I think the optimization may be to check if there is rabbit.Next.Equals(turtle) , but since none of the comments indicate this, I wonder if I am missing something.

Answer 1

The rabbit will never jump over the turtle, because the difference between the speed is 1.

The rabbit enters the loop first, then the tortoise. As soon as the turtle enters the loop, the difference between the rabbit and the turtle is resolved, and you might think that the rabbit lies behind the turtle. Then the difference simply decreases by 1 for each step.

Thus, the total steps will not exceed N, and therefore, this is O (n).

Answer 2

The simulation of a small hand should show you that although the rabbit can skip the turtle once, the second time through the loop, he will step on it (so to speak). (EDIT: this applies as soon as the rabbit and the turtle are in the loop, which will happen in no more than O (N) iterations.) Since O (2 * N) = O (N), it is still the O (N) algorithm .

Good algorithm. +1 for the link.

Answer 3

The rabbit cannot jump over the turtle, as the turtle is also moving. In ASCII text:

 R _ T RT X 

We put it differently, while the rabbit is behind the turtle, each loop iteration reduces their distance by 1. Therefore, there will be an iteration where the distance becomes exactly equal to 0.

Answer 4

There are two situations:

• There is an even number of nodes and
• There is an odd number of nodes.

Consider both.

In 1, we have the following:

TR xx then x T x R then x RT x then xxx RT

In 2 we have the following: TR x then RT x then xx RT

Given that a rabbit and a hare can only move with a maximum increment of two, these are the only two conditions that are worth noting. There is probably correct inductive evidence here, but showing the phases, explains why this works, even if the rabbit misses the turtle. A rabbit can only miss a turtle if it is behind the turtle, and if it is behind the turtle, either it will not miss or it will collide.

When the rabbit skips the turtle, as in 1, we only need N+1 movements of the turtle and the rabbit, so 2N+2 for N is the length of the list, which is O(N)

Answer 5

This algorithm becomes clearer if instead you run a rabbit and a turtle on the same node. When the turtle moved N nodes forward, the rabbit moved 2N nodes forward. If there is a cycle of length N, then the turl will return to the starting point after N moves, and the movement of the 2N rabbit will also land on the start node, bypassing the cycle twice.