Time complexity of depth-first graph algorithm

Question

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

Solution 1

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.

Solution 2

it will be O(n+m) if the graph is given in the form of adjacency list but if the graph is in the form of adjacency matrix then the complexity is O(n*n), as we have to traverse through the whole row until we find an edge.

Comments

[Learner]

respected sir, I am new to complexity analysis,actually i am doing a project on OS,i am trying to find the cycles in resource allocation graph ...i am finding cycles using a modification of depth first search..i am trying to compare the complexity of this algorithm with banker's algorithm..can you give mathematical derivation of "avergae case performance"

[Christopher Creutzig]

“Average case performance” is the expected value (that is a term from probability theory) of the running time over some assumed probability distribution of inputs.