Big-O notation for nested loops that might skip iterations
If the average number of times the inner loop is $O(f(n))$ then the total complexity is $O(n \times f(n))$.

Finding that average can be tricky when the condition is not trivial. however assuming that it never drops a loop will give you a worst case. This worst case will also be valid when the amount of inner loops skipped is a constant factor.

However in the first example the loop can be simplified to

for (var i = 0; i &lt; n; i++) {
  visited[i] = true;

  for (var j = i+1; j &lt; n; j++) {
      //...
  }
}


This is $O(n^2)$. Because $\Sigma_{i=0}^n i = \frac{n(n+1)}{2} = O(n^2)$