ericdrowell/BigOCheatSheet — pull request #9 by qpleple (2013-05-04 16:07:16+00:00)
Title: DFS and BFS for graphs

Algorithms DFS and BFS are primarily for graphs. Time and space complexities should be expressed in terms of the numbers of vertices |V| and the number of edges |E|.

The real complexity of DFS and BFS is O(|V| + |E|).
The time complexity for DFS and BFS given by Wikipedia makes the assumption that |E| > |V| and simplify |V| + |E| = O(|E|). But it's not always the case: if the graph has |V| = 1,000,000 vertices but just 10 edges, well DFS and BFS will have to go trough all the vertices before finishing, so it's certainly not O(|E|).

Most Computer Science books are reporting O(|E| + |V|) for DFS/BFS. See for example
> S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Algorithms
> (used at Berkeley and UC San Diego)
> see section 3.2.2. at http://www.cs.berkeley.edu/~vazirani/algorithms/chap3.pdf