motatoes's blog

How is the complexity of this algorithm O(|v||v| + |v||E|)
By motatoes, history, 6 years ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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|)

→ Reply