# Time complexity of Depth First Search [closed]

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

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 1-3 and 5-7 are O(V), exclusive of the time to execute the calls to DFS-VISIT(). In DFS-VISIT(), lines 4-7 are 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 DFS() is O(V + E).

I don't understand how that came about. DFS-VISIT() is called inside DFS(). So, if lines 5-7 of DFS() are O(V) and DFS-VISIT() is O(E), then shouldn't the total time complexity of DFS() be O(VE)?

• Cormen is only the first listed author. Jul 16, 2016 at 8:56
• Welcome to Computer Science! Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck!
– Raphael
Jul 16, 2016 at 13:23
• Could you give the exact quote of the text you don't understand? If it literally says "exclusive of the time to execute the calls to DFS-VISIT()" then that already answers your question: "exclusive of DFS-VISIT()" means that the time stated does not include the time taken by DFS-VISIT(). Jul 20, 2016 at 16:10

The book is counting the number of times each line is executed throughout the entire execution of a call of DFS, rather than the number of times it is executed in each call of the subroutine DFS-VISIT. Perhaps the following simpler example will make this clear:

PROCEDURE A(n)
1  global = 0
2  for i from 1 to n:
3      B(i)
4  return global

PROCEDURE B(i)
1  global = global + 1


In each execution of A, line 1 of B is executed $n$ times, and B itself is executed $n$ times. Nevertheless, the running time is $O(n)$ rather than $O(n^2)$.

Here is another example, in which an array $T[1\ldots n]$ is involved.

PROCEDURE COUNT(n, T[1...n]):
1  count = 0
2  index = 1
3  while index <= n:
5    count = count + 1
6    index = index + 1
7  return count - 1


The procedure COUNT counts the number of 1s in the input array T. Even though ADVANCE could be called up to $n$ times by COUNT and the worst-case running time of ADVANCE is $O(n)$, lines 1–2 of ADVANCE run at most $n$ times, and so the overall running time is $O(n)$ rather than $O(n^2)$.
• Um... I still can't understand. Time complexity for B() is O(1), so if i is called from 1 to n, then it's n-times O(1) -> O(n). You say line 1 of B is executed n times and B itself is executed n times, but aren't they the same thing? Jul 16, 2016 at 10:38
• Yuval sir@ i have got a doubt.In your provided Example algorithm, what if $A$ is called $n$ times which implies $O(n^{2})$.sir please help me out ! Jul 28, 2017 at 11:23
• Running a $\Theta(f(n))$ procedure $g(n)$ times takes time $\Theta(f(n)g(n))$. Jul 28, 2017 at 12:14