Menu
I am starting to learn time complexity, and I looked in the examples for the time complexity for some simple sort.
I wanted to know how do we calculate average time complexity for a depth-first search in a graph with |V|=n and |E|=m,let the start node be 'u' and end node be 'v'.
384
For a directed graph, the sum of the sizes of the adjacency lists of all the nodes is E(total number of edges). So, the complexity of DFS is O(V + E). Show activity on this post. It's O(V+E) because each visit to v of V must visit each e of E where |e| <= V-1.
Time Complexity of BFS = O(V+E) where V is vertices and E is edges. Time Complexity of DFS is also O(V+E) where V is vertices and E is edges.
The space complexity for DFS is O(h) where h is the maximum height of the tree.
Complexity Of Depth-First Search Algorithm If the entire graph is traversed, the temporal complexity of DFS is O(V), where V is the number of vertices.
The time complexity for DFS is O(n + m). We get this complexity considering the fact that we are visiting each node only once and in the case of a tree (no cycles) we are crossing all the edges once.
For example, if the start node is u, and the end node is v, we are thinking at the worst-case scenario when v will be the last visited node. So we are starting to visit each the first neighbor's of u connected component, then the second neighbor's connected component, and so on until the last neighbor's connected component, where we find v. We have visited each node only once, and didn't crossed the same edge more than once.
105
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
