Please forgive me for asking a novice question, but I'm a beginner at algorithms and complexities, and it's sometimes hard to understand how the complexity for a specific algorithm has come about.
I was reading the DFS algorithm from Introduction to Algorithms by Cormen, and this was the algorithm:
G -> graph G.V -> set of vertices in G u.π -> parent vertex of vertex u G.Adj[u] -> adjacency list of vertex u DFS(G) 1 for each vertex u ∈ G.V 2 u.color = WHITE 3 u.π = NIL 4 time = 0 5 for each vertex u ∈ G.V 6 if u.color == WHITE 7 DFS-VISIT(G,u) DFS-VISIT(G,u) 1 time = time + 1 // white vertex u has just been discovered 2 u.d = time 3 u.color = GRAY 4 for each v ∈ G.Adj[u] // explore edge u 5 if v.color == WHITE 6 v.π = u 7 DFS-VISIT(G,v) 8 u.color = BLACK // blacken u; it is finished 9 time = time + 1 10 u.f = time
It then said lines
O(V), exclusive of the time to execute the calls to
O(E), because the sum of the adjacency lists of all the vertices is the number of edges. And then it concluded that the total complexity of
O(V + E).
I don't understand how that came about.
DFS-VISIT() is called inside
DFS(). So, if lines
O(E), then shouldn't the total time complexity of