# Time complexity of BFS in O(b^n) - Constant of Big-O-Notation?

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

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