My understanding is that iterative deepening search is roughly equivalent to breadth-first search, except instead of keeping all visited nodes in memory, we regenerate nodes as needed, trading off memory for time.
The $(i+1)$th layer of a tree has about as many nodes as the entire rest of the tree before it*. Thus, on each iteration, iterative-deepening effectively has to expand the $(i+1)$th layer twice whereas breadth-first search only has to expand it once. So IDS takes at most twice as long as BFS. Is this correct?
* A proof of this statement is as follows: in a tree with branching factor $b$, the $i$th layer has $b^i$ nodes. The number of nodes up to and including the $i$th node is given by the $i$th partial sum of the geometric series, $\frac{b^{i+1} - 1}{b-1}$, which is strictly less than the number of nodes in the $(i+1)$th layer ($b^{i+1}$)
Please let me know if all this is correct and whether clarifications are needed anywhere to make it more rigorous.
