0
$\begingroup$

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?

enter image description here Image Reference

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!

$\endgroup$
1
  • $\begingroup$ $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$ $\endgroup$
    – Alberto
    Sep 5, 2023 at 0:45

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .