# What does the branching factor mean in the time complexity of Breadth-First Search (BFS)

Can someone explain where my math is off here?

I am confused on the b - Branching Factor and how to calculate the worst-case scenario when running BFS. In a worst-case scenario BFS would have to hit every single node from the root node to the goal node giving the complexity of 1 (root node) + b (number of nodes at depth 1) + b^2 (number of nodes at depth 2) + ... + b^d = b^d.

Based on the following image does that mean the Time Complexity is has an upper bound of O(b^d) = O(2^4) = 16 nodes + 1 = 17 Nodes?

Of course, if this was a complete binary tree with max nodes at depth of 4 there would be a total of 1 + 2 + 4 + 8 + 16 = 31 Nodes so the previous complexity does not make sense.

Thank You!

• $O(.)$ does not give you the worst case in an exact sense, but in an asymptotic sense, indeed it can be off by any constant, so $O(b^2)$ might even be $1000000\cdot b^d$ Sep 5, 2023 at 0:45

Math is just fine. Its all about the definition of $$\mathrm{O}(\cdot)$$. Checkout the wiki page about Big-O Notation.

Basically, your function $$T(b) = 1 + b + b^{2} + \cdots + b^{d}$$ belongs to the class of functions $$\mathrm{O}(b^{d})$$ if its upper bound is at most $$b^{d}$$ multiplied by some constant.

Note that: $$T(d) = 1 + b + b^{2} + \cdots + b^{d} \leq (d+1)b^{d},$$ which means that $$T(d) \in \mathrm{O}(b^{d})$$.

You could also obviously say that $$T(d) \in \mathrm{O}(b^{d+1})$$. If you want to be more specific about the complexity class to which your function belongs, then you can use Big-Theta Notation instead.

Your function $$T(b) = 1 + b + b^{2} + \cdots + b^{d}$$ belongs to the class of functions $$\mathrm{\Theta}(b^{d})$$ if its upper bound is at most $$b^{d}$$ multiplied by some constant and its lower bound is at least $$b^{d}$$ multiplied by some constant.

You have: \begin{align} T(d) &= 1 + b + b^{2} + \cdots + b^{d} \leq (d+1)b^{d} \\ T(d) &= 1 + b + b^{2} + \cdots + b^{d} \geq b^{d}, \end{align} which means that $$T(d) \in \mathrm{\Theta}(b^{d})$$.

HOWEVER, you can still say that $$T(d) \in \Theta(b^{d+1})$$.... \begin{align} T(d) &= 1 + b + b^{2} + \cdots + b^{d} \leq b^{d+1} \\ T(d) &= 1 + b + b^{2} + \cdots + b^{d} \geq \frac{1}{b}b^{d+1}. \end{align}

So, people mostly just say that the complexity class is "exponent of $$b$$", without thinking too much whether the power is $$d$$ or $$d+1$$.

Also this youtube video is highly recommended.