19

I know there's a similar question in stack overflow, where one person has asked, why time complexity of BFS/DFS is not simply O(V).

The appropriate answer given was that E can be as large as V^2 in case of complete graph, and hence it is valid to include E in time complexity.

But, if V cannot be greater than E+1. So, in that case not having V in the time complexity, should work?

axiom
  • 8,765
  • 3
  • 36
  • 38
Sandy
  • 466
  • 6
  • 15

2 Answers2

16

If it is given that E = kV + c, for some real constants k and c then,
O(E + V) = O(kV + c + V) = O(V) = O(E) and your argument is correct.

An example of this is trees.

In general (i.e., without any prior information), however, E = O(V^2), and thus we cannot do better than O(V^2).

Why not write just O(E) always?

EDIT: The primary reason for always writing O(E + V) is to avoid ambiguity.

For example, there might be cases when there are no edges in the graph at all (i.e. O(E) ~ O(1)). Even for such cases, we'll have to go to each of the vertex (O(V)), we cannot finish in O(1) time.

Thus, only writing O(E) won't do in general.

axiom
  • 8,765
  • 3
  • 36
  • 38
  • 1
    So, can I simply say O(E) as time complexity for BFS? – Sandy Nov 07 '14 at 17:33
  • 2
    @Sandy only if the above conditions are satisfied. In general case, there might be no edges, still you'll have to go to each vertex, thus we write `O(V + E)`. – axiom Nov 07 '14 at 19:09
  • That explains. But, now I have a new question. Can we do a BFS on a graph with no edges? How do I parse all the vertices if there are not connected? – Sandy Nov 07 '14 at 19:22
  • @Sandy Just go to each vertex, check its neighbors. Since there are no edges, there will be no neighbors. BFS remains defined. – axiom Nov 07 '14 at 19:27
  • I don't get it. Let's say there are 30 edges, and 200 vertices. From your start vertex, wouldn't you only explore 30 other vertices before you quit? That sounds like O(E), not O(V+E) – Nicholas Pipitone Nov 05 '19 at 05:30
  • @axiom So does O(V+E) in fact mean O(num_disconnected_vertices + E) ? I know that the former is an upper bound of the latter, but it is confusing because it looks like that we process *every* edge and then do extra processing on *every* vertex, which is not true. – Alan Evangelista Dec 04 '19 at 13:40
  • @AlanEvangelista `O(V + E)` is correct, not an overestimate. However you're defining a "disconnected" vertex, if we let `V = V_c + V_d` as the sum of the "connected" and "disconnected" vertices respectively, then `V_c` is at most `O(E)`, so `O(V + E)` is `O(V_d + V_c + E)`, which is at most `O(V_d + E + E)` or just `O(V_d + E)`, giving the bound from the other direction. `O(V + E)` does not imply you are processing *every* vertex plus *every* edge - it's an asymptotic bound. – kaya3 Jan 27 '20 at 21:42
  • amazing answer, anyone looking for additional help checkout: https://stackoverflow.com/questions/63321659/why-is-the-complexity-of-bfs-ove-instead-of-oe/63322046#63322046 – csguy Aug 09 '20 at 02:54
  • 4
    How would you "go to each vertex" when you can't find them via edges? This answer is incorrect. – Matt Timmermans Aug 09 '20 at 04:59
  • 1
    @MattTimmermans `for source in V: dfs(source)`. What is the time complexity of this loop in a graph where `|E|` = 0? – axiom Aug 09 '20 at 21:57
  • 1
    @axiom nobody asked about running a search from every possible vertex. – Matt Timmermans Aug 09 '20 at 23:46
  • 1
    @MattTimmermans I think you might be confusing the notion of complexity here. The question is: you're given a graph with V vertices and E edges. What would be the time complexity of running BFS or DFS? This is not the same as asking: can you construct a graph for which BFS would take `O(1)`? The question is about the worst case. – axiom Aug 11 '20 at 01:08
  • @axiom and nobody said the complexity of BFS was O(1) – Matt Timmermans Aug 11 '20 at 01:14
1

V has to be included because both BFS and DFS rely on arrays of size |V| to track which vertices have been processed/discovered/explored (whatever the case may be). If a graph has 0 edges and 100000 vertices, such arrays will still take more time to initialize than they would if there were only 5 vertices. Thus, the time complexities of BFS and DFS scale on |V|.

A K
  • 35
  • 7
  • You can implement BFS or DFS using a hashtable instead of an array, so that the initialisation takes O(1) time instead of O(V). – kaya3 Jan 27 '20 at 21:38
  • Do you mean inserting each vertex into the hash table (i.e. using it as an unordered map from a vertex to a boolean)? – A K Jan 29 '20 at 01:28
  • The keys in the hashtable are the visited vertices; a vertex is visited if and only if it is present in the hashtable. That way you can start with an empty hashtable (i.e. no vertices are visited yet), and you don't have to mark each vertex as "not visited yet" explicitly. I was thinking of the hashtable as the implementation of an unordered set rather than a map, but if there are different states (e.g. pre-visited vs. post-visited), for example, then a map could be more useful. – kaya3 Jan 29 '20 at 01:37
  • @kaya3 how big is your hash table? Did you initialize it? :) OK OK, if you use a dynamically growing hash table then the complexity of BFS is expected O(E) not O(V+E). That's just not the usual implementation, and for good reason. – Matt Timmermans Aug 11 '20 at 01:28
  • @MattTimmermans It is quite usual to implement BFS and DFS using a dynamically-growing hashtable if you are writing in a higher-level language where this is the data structure used for the built-in set type. For example, two of the top three Google results for 'depth first search python' initialise `visited = set()`, links [here](https://www.educative.io/edpresso/how-to-implement-depth-first-search-in-python) and [here](https://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/). – kaya3 Aug 11 '20 at 01:49
  • @kaya3 yes, that's true – Matt Timmermans Aug 11 '20 at 01:55