1

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$.

DasElias
  • 111
  • 2

1 Answers1

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)$.

cinch
  • 11,000
  • 3
  • 8
  • 17