Is the Turtle and Rabbit algorithm always O(N)?

Question

I'm going to preface this with the fact that I am not completely knowledgeable on Big O Notation, so maybe my thinking about this is off.

I was randomly browsing SO when I came upon a question about detecting infinite loops in Linked Lists. This pointed me to the algorithm here known as the 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 in relation to how many elements are in the list.

However, unless I am looking at things wrong, the rabbit variable is always skipping 1 node (so it's "faster") which means that it has the potential to skip over the turtle node, thus having the potential of looping around the infinite loop 1 or more times before it becomes the same node as the turtle variable, which would mean the worst-case scenario isn't O(N).

Am I missing something? I guess an optimization might be to check if rabbit.Next.Equals(turtle) as well but as none of the comments point this out so I am wondering 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 goes in the loop first, then the turtle. As soon as the turtle goes in the loop, the difference of the rabbit and the turtle is decided, and you can consider the rabbit is behind the turtle. Then is difference is simply decreased by 1 for each step.

So the total steps will not exceed N, and thus it is O(n).

Answer 2

A little hand simulation should show you that while rabbit can skip over the turtle once, the second time around the loop, it will step on it (so to speak). (EDIT: this applies once both the rabbit and turtle are in the loop, which will happen in at most O(N) iterations.) Since O(2*N) = O(N), it's still an O(N) algorithm.

Nice algorithm, too. +1 for the link.