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

Full article content could not be extracted automatically. Read the original below.