I was reading Donal B .Johnson's paper for finding all elementary circuits in a directed graph, http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF
In this paper he mentioned that worst case for Tarjan Algorithm is O(V*E (c+1)) While everywhere else it is shown as O(V+E), Johnson paper has taken couple of example to prove that point , Like Fig 1 and Fig 2 on the paper.
Fig 2 example which is fairly similar , after finding first cycle 1...k in O(k) time , now as per my understanding all the other vertcies will simply return as their index is already defined and it should take another k time for k vertices, so to sump up it should 2k times instead of k**2 , am I missing some point here ?
Please suggest with some example , Thanks
"Tarjan's algorithm" is in this case not the algorithm for strongly connected components. It is his algorithm for enumerating elementary circuits. However, in the original paper, this method is noted as having a tight worst case O((V + E) * (C + 1)) time. It is interesting to note that the argument Tarjan uses to prove this bound (O(V + E) time between finding two circuits) is suddenly changed in Johnson's paper (O(V * E) time between finding two circuits). I'm not familiar with either of these algorithms, so I can't say which one is correct. A quick search seems to regard Johnson's algorithm as being asymptotically faster (even though both methods claim the same time complexity), but nowhere could I find a source that disproves the time complexity in Tarjan's paper.