Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-31T20:48:16.327Z
Answers.LastActivityDate: 2024-03-31T20:48:16.327Z
Answers.UserDisplayName: cinch
Body: <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>
  
Tags: <search><breadth-first-search>
Title: Time complexity of BFS in O(b^n) - Constant of Big-O-Notation?
UserDisplayName: DasElias
ThreadText: # 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)$.
  
  
  ---
  
  