# algorithms – Runtime Complexity of finding a loop in an array

Having a hard time understanding the runtime complexity of the following algorithm:

``````public class Solution {
public boolean circularArrayLoop(int() nums) {
int n = nums.length;
if(n < 2){
return false;
}
for(int i = 0; i < n; i++){
if(nums(i) == 0){
continue;
}
int slow = i, fast = advance(nums, i);
while(nums(slow) * nums(fast) > 0 && nums(advance(nums, fast)) * nums(slow) > 0){
if(slow == fast){
//one element loop does not count
if(slow == advance(nums, slow)){
break;
}
return true;
}
slow = advance(nums, slow);
fast = advance(nums, (advance(nums,fast)));
}

//loop not found, set all the elements along the way to 0
slow = i;
int val = nums(i);
while(nums(slow) * val > 0){
int next = advance(nums, slow);
nums(slow) = 0;
slow = next;
}

}
return false;

}
public int advance(int() nums, int i){
int n = nums.length;
return i + nums(i)  >= 0 ? (i+nums(i)) % n : n + ((i + nums(i)) %n);
}
}
``````

Been told that the complexity should be $$O(n)$$ because each node is visited at most four times by slow, by fast, be marking zero, be zero checking. Cannot quite agree, because even it is marked zero, the rest of the nodes still have to check whether it is zero or not. So you have to check it at least $$n-1$$ times.