Question

Let G (V, E) be a directed graph with n vertices and m edges. It is known that in dfsTrace of G the function dfs is called n times, once for each vertex It is also seen that dfs contains a loop whose body gets executed while visiting v once for each vertex w adjacent to v; that is the body gets executed once for each edge (v, w). In the worst case there are n adjacent vertices. What do these facts imply about the best asymptotic order (big O and/or big Θ) we can derive in terms of n and m about the worst-case time for dfsTrace? Explain your answer briefly

Answer 1

First, dfsTrace calls the dfs function times. Now, inside each dfs call, there is a loop whose body gets executed once for each edge. Hence the number of times the loop runs is exactly . Hence, the runtime of each dfs call is $\Theta(m)$. Thus, the total time complexity for the dfsTrace function is $n \cdot \Theta(m) = \Theta(n \cdot m)$ .

This is the worst case complexity of the dfsTrace function.

Comment in case of any doubts.