# Why is the running time for BFS $O(b^{d+1})$?

In my Artificial Intelligence class, in a section on Uninformed Search Algorithms, the textbook for the class (and as was discussed in lecture) the running time for Breadth First Search is listed as being: $O(b^{d+1})$ with the following explanation:

Normally (or at least in my experience thus far in Algorithms) I've seen the running time of BFS to be $O(V+E)$ so why is it different here. Is this a special case?

• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! Oct 9, 2016 at 20:16
• Please cite the textbook properly so I can tell people to avoid it. Oct 9, 2016 at 20:21
• It seems to be "Artificial Intelligence: A modern approach", by Stuart Russell and Peter Norvig. Oct 9, 2016 at 20:25

This represents a difference between the kinds of problems the CS algorithms community usually uses BFS to solve, vs the kinds of problems the CS artificial intelligence community usually uses BFS to solve.

The algorithms community typically is focused on the case where we have a finite graph, and where we're going to run some algorithm that probably visits everything in the graph. We measure the number of vertices ($V$) and the number of edges ($E)$, and the running time is measured in terms of these two parameters. Also, the algorithms community usually analyzes the case where we run BFS until every vertex in the graph has been visited. If this is the goal, and those are the parameters we care about, the running time to visit every vertex is indeed $O(V+E)$.

The artificial community typically considers a different scenario: we have an infinite or very large graph, and we're not going to visit all of it; we're going to visit only a tiny fraction of the graph, only as much as necessary until we can find one node with a particular property (a target node / goal node). Think of the state space of a game like chess, or the 15-puzzle, or something like that. In addition, in the cases that typically arise in artificial intelligence, usually the portion of the graph that we're going to visit looks sorta like a tree: each vertex has on average about $b$ edges leading out of it. So in this situation, a bound like $O(V+E)$ is not helpful: it is a valid upper bound, but it is extremely loose -- the number of states (vertices) you actually need to visit might be much smaller than the total number of states (vertices) that exist. So, in AI applications, we usually want a better estimate of the number of states visited. That's what leads to the $O(b^d)$ estimate.

Both upper bounds are valid, in the situation where they apply. But the two situations they're focused on are very different. It's the same algorithm (BFS), applied in two different contexts... and because of some differences in the characteristics, it makes sense to measure its running time differently in the two settings.

• So the running time of $O(b^d)$ is actually linear then? Oct 11, 2016 at 17:25
• @loremIpsum1771, it's not linear in $b$ or $d$, but it is at most linear in $V$.
– D.W.
Oct 11, 2016 at 22:03
• So would the tight bound be referred to as constant? Oct 12, 2016 at 3:30
• @loremIpsum1771, no. Constant would be $O(1)$.
– D.W.
Oct 12, 2016 at 4:30
• But then if its neither linear nor constant, how would you refer to it? Oct 14, 2016 at 22:46

The bounds $O(|V|+|E|)$ and $O(b^d)$ are talking about different things. The former is appropriate when you know what $V$ and $E$ are in advance, and they're both finite. The latter is appropriate when the graph is only defined implicitly and may be infinite, or where you've decided in advance that you're only going to search to a fixed depth.

An example of the case where the $O(b^d)$ bound is appropriate is chess.1 Here, you're not given the state graph: rather, you're given the initial position and the rules to generate new positions from wherever you are at the moment. The number of reachable positions is so large that a bound of $O(|V|+\cdots)$ is meaningless. For the same reason, we're not going to search the whole graph for checkmate. Instead, we'll fix some depth $d$ and say, "OK, looking $d$ moves ahead, what's the best position I can reach?"

1 The adversarial nature of chess means you have to use minimax rather than BFS, but the principles are the same, as they apply to this question. Using BFS would assume that your opponent is co-operating to help you win as quickly as possible.

$O(b^d)$ is a correct if crappy (read: rough) bound: it bounds the number of nodes from above with the complete tree with height $d$.

Since $\log n \leq d \leq n$ (with $n$ the number of nodes), you can see that the bound is tight for $d \in \Theta(\log n)$ but is not for $d \in \omega(\log n)$.

Don't let this source confuse you: BFS, if implemented in a reasonable way, has running time in $\Theta(n)$ (on trees) and space usage in $O(n)$ (proportional to the maximum level width, in fact).

• So you're saying that $b^d$ is actually less than $n$ ? Also, when would the height of the tree ($d$) be larger than $log(n)$? Oct 9, 2016 at 21:24
• @loremIpsum1771 1) No, I'm saying that maybe $n \ll b^d$. 2) Whenever the tree is not balanced, which you have to take extra care to maintain. For instance, if your tree is an MST or tree of shortest paths, you don't know a bound on its height (but $n$) per se. Oct 9, 2016 at 22:35
• The bound isn't crappy if $V$ is infinite, if the search is being performed to fixed depth, or if the graph is implicitly defined. Oct 10, 2016 at 7:46
• Also, how do you get space usage O(max level width) if your graph isn't a tree? Don't you need to keep track of all visited nodes? Oct 10, 2016 at 7:47
• @DavidRicherby True, I did not think of that. Yours and D.W.'s answers are probably better. Oct 10, 2016 at 18:27

It seems that the author later addresses what D.W. and David said, at section 3.3.2, Artificial Intelligence: A modern approach, 3rd Edition.

Time and space complexity are always considered with respect to some measure of the problem difficulty. In theoretical computer science, the typical measure is the size of the state space graph, $|V | + |E|$, where V is the set of vertices (nodes) of the graph and E is the set of edges (links). This is appropriate when the graph is an explicit data structure that is input to the search program. (The map of Romania is an example of this.) In AI, the graph is often represented implicitly by the initial state, actions, and transition model and is frequently infinite. For these reasons, complexity is expressed in terms of three quantities: b, the branching BRANCHING FACTOR factor or maximum number of successors of any node; d, the depth of the shallowest goal DEPTH node (i.e., the number of steps along the path from the root); and m, the maximum length of any path in the state space. Time is often measured in terms of the number of nodes generated during the search, and space in terms of the maximum number of nodes stored in memory. For the most part, we describe time and space complexity for search on a tree; for a graph, the answer depends on how “redundant” the paths in the state space are.