Краткое содержание

Раздел 3.4.1 (Поиск в ширину) книги «Искусственный интеллект: Современный подход» (4-е издание, Норвиг и Рассел) оценивает общее количество сгенерированных узлов для анализа временной сложности следующим образом:$$ 1+b+\dots + b^d = O(b^d) $$Я понимаю, как получена левая часть уравнения. Однако, хотя интуитивно ясно, что это выражение действительно находится в $O(b^d)$, меня интересует формальное обоснование с использованием определения нотации Big-O. Таким образом, я хочу найти константу $k$, для которой выполняется следующее:$$ 1+b+\dots + b^d \leq k * b^d $$Я бы упростил левую часть следующим образом, используя формулу частичных сумм геометрической прогрессии для $b \neq 1$:$$ \frac{b^{d+1}-1}{b-1} \leq k * b^d $$Затем я прихожу к следующему выражению:$$ b^{d+1} - 1 \leq k * b^{d+1} - k * b^{d} $$Однако я не уверен, как мне действовать дальше, чтобы оценить константу $k$.