Editing Iterative deepening depth-first search (section)

==== Proof ====

In an iterative deepening search, the nodes at depth <math>d</math> are expanded once, those at depth <math>d - 1</math> are expanded twice, and so on up to the root of the search tree, which is
expanded <math>d+1</math> times.<ref name="re1985"/>{{rp|5}} So the total number of expansions in an iterative deepening search is

:<math>b^{d} + 2b^{d-1} + 3b^{d-2} + \cdots + (d-1)b^{2} + db +  (d + 1) = \sum_{i=0}^d (d+1-i)b^i</math>

where <math>b^{d}</math> is the number of expansions at depth <math>d</math>, <math>2b^{d - 1}</math> is the number of expansions at depth <math>d - 1</math>, and so on. Factoring out <math>b^{d}</math> gives

:<math>b^{d}(1 + 2b^{-1} + 3b^{-2} + \cdots + (d-1)b^{2 - d} + db^{1 - d} + (d + 1)b^{-d}) </math>

Now let <math>x = \frac{1}{b} = b^{-1}</math>. Then we have

:<math>b^{d}(1 + 2x + 3x^2 + \cdots + (d-1)x^{d - 2} + dx^{d - 1} + (d + 1)x^d)</math>

This is less than the infinite series

:<math>b^{d}(1 + 2x + 3x^2 + 4x^3 + \cdots ) = b^{d} \left( \sum^{\infty}_{n=1}n x^{n-1} \right)</math>

which [[Geometric series#Geometric power series|converges]] to

:<math>b^d (1 - x)^{-2} = b^d  \frac{1}{(1-x)^2}</math>, for <math>abs(x) < 1</math>

That is, we have

<math>b^{d}(1 + 2x + 3x^2 + \cdots + (d-1)x^{d - 2} + dx^{d - 1} + (d + 1)x^d) \leq b^d (1 - x)^{-2}</math>, for <math>abs(x) < 1</math>

Since <math>(1 - x)^{-2}</math> or <math>\left(1 - \frac{1}{b} \right)^{-2}</math> is a constant independent of <math>d</math> (the depth), if <math>b > 1</math> (i.e., if the branching factor is greater than 1), the running time of the depth-first iterative deepening search is <math>O(b^d)</math>.