worst running time for finding SCC using DFS Kosaraju

Question

Kosaraju's algorithm states the following:

#Input is graph G
1-define G_rev (links in reversed order)
2-Find the finishing times for G_rev using DFS
3-Run DFS for G in sequence based on finishing time

The running time is O(n+m) where n is the number of vertices and m is number of edges. If I have a complete graph G (all nodes connected to all), the number of edges is m = n*n. What is the running time in this complete graph G? When I look into the DFS code in (1), I will start from node 1 (outer loop) and I will be visiting and completing all the other nodes. The outer loop will be going through all the other nodes and find that they are finished and skip them. The same apply for (2). It seems that I will not be visting n*n edges. If G is complete, there is only one SCC (whole graph) and the running time is O(n+m) and m < n*n . Is it correct?

Answer 1

This is correct. Your running time is O(n+m) = O(n²).

Note that if you know in advance your graph is complete, there's not much point in running SCC on it.