The running time of BFS is O(V+E) and that of DFS is Ө(V+E). As both DFS and BFS visit each vertex once and traverse all edges atmost twice, shouldn't the runtime of both be Ө(V+E)? Why are their running times different? In which scenarios are they different?
1 Answers
0
votes
From wikipedia,
"The time and space analysis of DFS differs according to its application area. In theoretical computer science, DFS is typically used to traverse an entire graph, and takes time Θ(|V| + |E|)"
The word typically leads to the case that this is just because of semantics. In the world of infinite memory, you could also typically use BFS for searching the whole graph, thus also having Ө(V+E).
Edit: Scenario in which they have different run time.
Suppose the Queue in which BFS is accessing is too large, that it have additional access time of O(log(K+E)). Then BFS's run-time would would be O(V + E + log(V+E)).
Whilst DFS will remain Θ(V+E) since the search is in low level cache.
