Time complexity of depth-first graph algorithm

algorithm time-complexity depth-first-search
Learner picture Learner · Apr 12, 2012 · Viewed 56.8k times · Source

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'.

Answer

gabitzish picture gabitzish · Apr 12, 2012

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.

Related questions

Time/Space Complexity of Depth First Search

I've looked at various other StackOverflow answer's and they all are different to what my lecturer has written in his slides. Depth First Search has a time complexity of O(b^m), where b is the maximum branching factor of …

Read More
Is the runtime of BFS and DFS on a binary tree O(N)?

I realize that runtime of BFS and DFS on a generic graph is O(n+m), where n is number of nodes and m is number of edges, and this is because for each node its adjacency list must be …

Read More
How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More