Why does the time complexity of DFS and BFS depend on the way the graph is represented?

In both cases, the runtime depends on how long it takes to iterate across the outgoing edges of a given node. With an adjacency list, the runtime is directly proportional to the number of outgoing edges. Since each node is visited once, the cost is the number of nodes plus the number of edges, which is O(m + n). With am adjacency matrix, the time required to find all outgoing edges is O(n) because all n columns in the row for a node must be inspected. Summing up across all n nodes, this works out to O(n²).

Hope this helps!

The time complexity for both DFS and BFS can be computed as follows:

Iterating every vertex once and its corresponding incident edges, so the total time complexity will be ->

Time Complexity = v1 + (incident_edges on v1) + v2 + (incident_edges on v2) + ...... + vn + ( incident_edges on vn)

Now this can be regrouped as -> (v1+v2+v3+.....vn) + (incident_edges on v1 + incident_edges on v2 + ..... incident_edges on vn)

Thus total time complexity would turn out to be = (v1+v2+v3+.....vn) + (incident_edges on v1 + incident_edges on v2 + ..... incident_edges on vn)

(v1 + v2 + ... + vn) = V or n (Total number of vertices)

For adjacency list representation :

(incident_edges on v1 + incident_edges on v2 + ..... incident_edges on vn) = E(Total number of edges)

Thus for adjacency list representation time complexity will be O(V+E)

For adjacency matrix representation :

To visit the neighbors of the corresponding node(Row) we need to iterate all the columns for the particular row which amounts to V

So, (incident_edges on v1 + incident_edges on v2 + ..... incident_edges on vn) = V + V + .... Vth time V) = V*V

Thus time complexity will be O(V + V^2) = O(V^2)