Why are there two listed time complexities for breadth-first search?

Question

The Wikipedia article on breadth-first search lists two time complexities for breadth-first search over a graph: O(|E|) and O(b^d). Later on the page, though, it only lists O(|E|).

Why are there two different runtimes? Which one is correct?

Answer 1

Both time complexities are correct, but are used in different circumstances to measure the time complexity relative to two different quantities. This has to do with the fact that the breadth-first search algorithm typically refers to two different related algorithms used in different contexts.

In one context, BFS is an algorithm that, given a graph and a start node in the graph, visits every node reachable from the start node by first visiting all nodes at distance 0, then distance 1, then distance 2, etc. until all nodes are visited. This will visit every node in the graph and in the process of doing so explore each node one and edge edge at most once (in the directed case) or twice (in the undirected case). By using queues to keep track of which nodes to explore next and using appropriate bookkeeping, the runtime will be O(|E| + |V|) (and with further optimizations, it will be O(|E|)).

In a different context, BFS is a search algorithm used to find the shortest path from some start node in a graph to a destination node in the graph. In this case, the algorithm stops running as soon as it discovers the destination node. This means that the runtime depends on how far away the destination node is from the source node. That distance in turn depends on the structure of the graph. If the graph is densely connected, the node can't be that far away, and if the graph is sparse, the node might be extremely distant. In this context, it's common to add in a parameter called the "branching factor" b, which describes the average or maximum number of edges adjacent to any node. This means that

• There is one node at distance 0 from the start node.
• There are at most b nodes at distance 1 from the start node.
• There are at most b² nodes at distance 2 from the start node.
• ...
• There are at most b^k nodes at distance k from the start node.

If we assume that the destination node is at distance d from the start node, then BFS will visit at most b⁰ + b¹ + ... + b^d = O(b^d) nodes during its search, spending O(b) time on each of them. Accordingly, the total runtime will be O(b^d).

In summary:

• The runtime of O(|E|) is typically used when discussing the algorithm when being used to explore the entire graph.
• The runtime of O(b^d) is typically used when discussing the algorithm when being used to find a specific node in the graph.

Hope this helps!