Answers.Body: <p>Math is just fine. Its all about the definition of <span class="math-container">$\mathrm{O}(\cdot)$</span>. Checkout the wiki page about <a href="https://en.wikipedia.org/wiki/Big_O_notation" rel="nofollow noreferrer">Big-O Notation</a>.</p>
  <p>Basically, your function <span class="math-container">$T(b) = 1 + b + b^{2} + \cdots + b^{d}$</span> belongs to the class of functions <span class="math-container">$\mathrm{O}(b^{d})$</span> if its upper bound is at most <span class="math-container">$b^{d}$</span> <strong>multiplied by some constant</strong>.</p>
  <p>Note that:
  <span class="math-container">$$ T(d) = 1 + b + b^{2} + \cdots + b^{d} \leq (d+1)b^{d}, $$</span>
  which means that <span class="math-container">$T(d) \in \mathrm{O}(b^{d})$</span>.</p>
  <p>You could also obviously say that <span class="math-container">$T(d) \in \mathrm{O}(b^{d+1})$</span>. If you want to be more specific about the complexity class to which your function belongs, then you can use <a href="https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation" rel="nofollow noreferrer">Big-Theta Notation</a> instead.</p>
  <p>Your function <span class="math-container">$T(b) = 1 + b + b^{2} + \cdots + b^{d}$</span> belongs to the class of functions <span class="math-container">$\mathrm{\Theta}(b^{d})$</span> if its upper bound is at most <span class="math-container">$b^{d}$</span> multiplied by some constant <strong>and its lower bound is at least <span class="math-container">$b^{d}$</span> multiplied by some constant</strong>.</p>
  <p>You have:
  <span class="math-container">\begin{align}
  T(d) &amp;= 1 + b + b^{2} + \cdots + b^{d} \leq (d+1)b^{d} \\
  T(d) &amp;= 1 + b + b^{2} + \cdots + b^{d} \geq b^{d},
  \end{align}</span>
  which means that <span class="math-container">$T(d) \in \mathrm{\Theta}(b^{d})$</span>.</p>
  <p><strong>HOWEVER</strong>, you can still say that <span class="math-container">$T(d) \in \Theta(b^{d+1})$</span>....
  <span class="math-container">\begin{align}
  T(d) &amp;= 1 + b + b^{2} + \cdots + b^{d} \leq b^{d+1} \\
  T(d) &amp;= 1 + b + b^{2} + \cdots + b^{d} \geq \frac{1}{b}b^{d+1}.
  \end{align}</span></p>
  <p>So, people mostly just say that the complexity class is &quot;exponent of <span class="math-container">$b$</span>&quot;, without thinking too much whether the power is <span class="math-container">$d$</span> or <span class="math-container">$d+1$</span>.</p>
  <p>Also this <a href="https://youtu.be/FUaY0N4qVPY?list=PLhMnuBfGeCDNgVzLPxF9o5UNKG1b-LFY9&amp;t=2460" rel="nofollow noreferrer">youtube video</a> is highly recommended.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-05T09:00:27.267Z
Answers.LastActivityDate: 2023-09-12T21:15:40.827Z
Answers.LastEditDate: 2023-09-12T21:15:40.827Z
Answers.UserDisplayName: pi-tau
Body: <p>Can someone explain where my math is off here?</p>
  <p>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.</p>
  <p>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?</p>
  <p><a href="https://i.sstatic.net/5tDv7.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5tDv7.png" alt="enter image description here" /></a>
  <a href="https://www.javatpoint.com/ai-uninformed-search-algorithms" rel="nofollow noreferrer">Image Reference</a></p>
  <p>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.</p>
  <p>Thank You!</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-05T00:45:32.550Z
Comments.Text: $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$
Comments.UserDisplayName: Alberto
Tags: <search><time-complexity><breadth-first-search>
Title: What does the branching factor mean in the time complexity of Breadth-First Search (BFS)
UserDisplayName: ImposterX1
ThreadText: # What does the branching factor mean in the time complexity of Breadth-First Search (BFS)
  
  (Asked by: username_0 on 2023-09-04)
  
  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](https://i.sstatic.net/5tDv7.png)](https://i.sstatic.net/5tDv7.png)
  [Image Reference](https://www.javatpoint.com/ai-uninformed-search-algorithms)
  
  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!
  
  **Tags:** search, time-complexity, breadth-first-search
  
  > **Comments:**
  > **username_1**: $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$  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2023-09-05. Score: 1 | Accepted answer
  
  Math is just fine. Its all about the definition of $\mathrm{O}(\cdot)$. Checkout the wiki page about [Big-O Notation](https://en.wikipedia.org/wiki/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](https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-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](https://youtu.be/FUaY0N4qVPY?list=PLhMnuBfGeCDNgVzLPxF9o5UNKG1b-LFY9&t=2460) is highly recommended.
  
  
  ---
  
  