Where Algorithmic Complexity is not a function of the number of loops

When we take a look at the above algorithm, we can see that there is an outer loop that runs from 1 to n, where n is the number of vertices. For each vertex, i, the algorithm calls DFS routine if i is not explored yet.

Here, the outer loop runs n times, and each inner loop examines on an average of the order of n vertices, but that said, the algorithmic complexity is not O(n^2).

While that may be how it looks like, on closer inspection, we can see that the outer loop doesn't invoke the DFS subroutine if the vertex i is already examined. So, here, for the cases where i is already explored, the work done by the outer loop is in fact, O(1). 

So, for example, the complexity is more like O(n/4) + O(n/2) + O(n/8) +  O (n/8) + m * O(1) which is O(n) or linear.