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

i'm going preface fact not knowledgeable on big o notation, maybe thinking off.

i randomly browsing when came upon question detecting infinite loops in linked lists. pointed me algorithm here known turtle , 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)) {       // faster moving node has caught slower moving node       return true;     } else if (rabbit.next == null) {       // reached end of list       return false;     } else {       turtle = turtle.next;       rabbit = rabbit.next.next;     }   }   // rabbit reached end   return false; } 

in article mentions o(n). understand o(n) means speed of algorithm grows linearly in relation how many elements in list.

however, unless looking @ things wrong, rabbit variable skipping 1 node (so it's "faster") means has potential skip on turtle node, having potential of looping around infinite loop 1 or more times before becomes same node turtle variable, mean worst-case scenario isn't o(n).

am missing something? guess optimization might check if rabbit.next.equals(turtle) none of comments point out wondering if missing something.

the rabbit never jump on turtle, because difference between speed 1.

the rabbit goes in loop first, turtle. turtle goes in loop, difference of rabbit , turtle decided, , can consider rabbit behind turtle. difference decreased 1 each step.

so total steps not exceed n, , o(n).