<p>Since the LHS of your first inequality only has a finite <span class="math-container">$(d+1)$</span> terms and <span class="math-container">$b,d$</span> are integers greater than <span class="math-container">$1$</span> in breadth-first search, your <span class="math-container">$k$</span> could be simply set as <span class="math-container">$(d+1)$</span> or anything greater to see both the time and space complexity is <span class="math-container">$O(b^d)$</span>.</p>

CC BY-SA 4.0
2024-03-31T20:48:16.327Z
2024-03-31T20:48:16.327Z
cinch
<p>Section 3.4.1 (Breadth-first search) of the book &quot;Artificial Intelligence: A Modern Approach&quot; (4th edition, by Norvig and Russell) estimates the total number of generated nodes for time complexity analysis as follows:</p>
<p><span class="math-container">$$
1+b+\dots + b^d = O(b^d)
$$</span></p>
<p>I understand how the term on the left side of the equation is obtained. However, while it seems intuitive that this expression is indeed in <span class="math-container">$O(b^d)$</span>, I am interested in a formal argumentation using the definition of Big-O-Notation. Hence, I want to find a constant <span class="math-container">$k$</span> for which the following holds:</p>
<p><span class="math-container">$$
1+b+\dots + b^d \leq k * b^d
$$</span></p>
<p>I would have simplified the left side as follows, using the formula for partial sums of a geometric series for <span class="math-container">$b \neq 1$</span>:
<span class="math-container">$$
1 * \left(\frac{b^{d+1}-1}{d-1}\right) \leq k * b^d
$$</span></p>
<p>Then, I end up with the following expression:</p>
<p><span class="math-container">$$
b^{d+1} - 1 \leq k * b^{d+1} - k * b^{d}
$$</span></p>
<p>However, I am unsure how I would proceed from here in order to estimate the constant <span class="math-container">$k$</span>.</p>

<search><breadth-first-search>
Time complexity of BFS in O(b^n) - Constant of Big-O-Notation?
DasElias
# Time complexity of BFS in O(b^n) - Constant of Big-O-Notation?

(Asked by: username_0 on 2024-03-31)

Section 3.4.1 (Breadth-first search) of the book "Artificial Intelligence: A Modern Approach" (4th edition, by Norvig and Russell) estimates the total number of generated nodes for time complexity analysis as follows:

$$
1+b+\dots + b^d = O(b^d)
$$

I understand how the term on the left side of the equation is obtained. However, while it seems intuitive that this expression is indeed in $O(b^d)$, I am interested in a formal argumentation using the definition of Big-O-Notation. Hence, I want to find a constant $k$ for which the following holds:

$$
1+b+\dots + b^d \leq k \* b^d
$$

I would have simplified the left side as follows, using the formula for partial sums of a geometric series for $b \neq 1$:
$$
1 \* \left(\frac{b^{d+1}-1}{d-1}\right) \leq k \* b^d
$$

Then, I end up with the following expression:

$$
b^{d+1} - 1 \leq k \* b^{d+1} - k \* b^{d}
$$

However, I am unsure how I would proceed from here in order to estimate the constant $k$.

**Tags:** search, breadth-first-search


---

## 1 answers

### Answer by username_1 on 2024-03-31. Score: 0

Since the LHS of your first inequality only has a finite $(d+1)$ terms and $b,d$ are integers greater than $1$ in breadth-first search, your $k$ could be simply set as $(d+1)$ or anything greater to see both the time and space complexity is $O(b^d)$.


---

