Why is time complexity for BFS/DFS not simply O(E) instead of O(E+V)?

Question

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?

Answer 1

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.

Answer 2

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