Hi CF
I'm taking this course on coursera called "algorithms on graphs". In these slides there is a description of a naive algorithm for calculating strongly connected components (SCC) on a directed graph (slide number 5):
I have a question regarding the complexity of this algorithm. We know that for each vertex V we need to explore all its neighbours so I assumed that its complexity is |V|^2 if the graph is fully connected?
Then for each neibghbour of v we must check that we can reach back to V, so what will the complexity be in this case?
My question is how can we prove that the complexity of this naive algorithm is P(|V||V| + |V||E|) where |V| is the number of vertices and |E| is the number of edges?
Assuming that explore(v) runs a simple DFS/BFS, which has complexity O(|V| + |E|), if we run explore(v) for every vertex v, then we have a complexity of O(|V|(|V| + |E|)) which is O(|V|2 + |V||E|)
Makes perfect sense, thanks