Iterative Deepening Time Complexity
Claim
Iterative deepening search (IDS) with branching factor \(b\) and solution depth \(d\) generates \(O(b^d)\) nodes, the same asymptotic count as BFS (Russell and Norvig 2020).
Proof
IDS runs a depth-limited search at each limit \(\ell = 0, 1, \ldots, d\). A depth-limited search to depth \(\ell\) on a tree of branching factor \(b\) visits at most
\[ 1 + b + b^2 + \cdots + b^\ell = \frac{b^{\ell+1} - 1}{b - 1} \leq \frac{b^{\ell+1}}{b-1} \]
nodes. Summing over all iterations \(\ell = 0\) through \(d\):
\[ N(b, d) = \sum_{\ell=0}^{d} (d - \ell + 1) \cdot b^\ell, \]
where the factor \((d - \ell + 1)\) counts how many times a node at depth \(\ell\) is visited across all iterations (it is visited in the runs for \(\ell, \ell+1, \ldots, d\), a total of \(d - \ell + 1\) times).
Expanding:
\[ N(b, d) = (d+1) b^0 + d \cdot b^1 + (d-1) b^2 + \cdots + 1 \cdot b^d. \]
Factor out \(b^d\):
\[ N(b, d) = b^d \sum_{k=0}^{d} (k+1) b^{-k} \;\leq\; b^d \sum_{k=0}^{\infty} (k+1) b^{-k}. \]
For \(b \geq 2\) the series converges:
\[ \sum_{k=0}^{\infty} (k+1) x^k = \frac{1}{(1-x)^2}, \quad x = \frac{1}{b}. \]
Therefore:
\[ N(b, d) \leq b^d \cdot \frac{1}{(1 - 1/b)^2} = b^d \cdot \frac{b^2}{(b-1)^2}. \]
The factor \(b^2/(b-1)^2\) is a constant depending only on \(b\), so
\[ N(b, d) = O(b^d). \quad \square \]
Overhead Relative to BFS
BFS generates exactly \(\sum_{\ell=0}^{d} b^\ell = (b^{d+1}-1)/(b-1) \approx b^d/(1-1/b)\) nodes. The ratio is:
\[ \frac{N(b,d)}{N_{\text{BFS}}} \approx \frac{b}{b-1}. \]
For \(b = 2\) the overhead is at most a factor of 2; for \(b = 10\) it is at most \(10/9 \approx 1.11\). The repeated work is negligible in practice.